Questions tagged [hypergraphs]

The tag has no usage guidance.

28 questions
117 views

Expander Graph from Hypergraph

I came up with this problem while thinking about an optimizing compiler. Let $H$ be a hypergraph. From this we construct a graph $G_H$ as follows the vertices are the hyperedges of the hypergraph. ...
175 views

Minimising the root-set of a spanning hyperforest of a hypergraph

I am interested in the complexity of a problem involving spanning hyperforests (a union of hypertrees, which covers all of the vertices) of a $k$-hypergraph. I describe the relevant definitions for ...
166 views

Reduction of graph chromatic number to hypergraph 2-colorability

I'm following this paper titled "Coverings and colorings of hypergraphs" by Lovasz 1973, which is referenced in Garey and Johnson's Computers and Intractability, for the Set Splitting Problem. In this ...
69 views

Almost regular subhypergraph of hypergraph with large minimal degree

I am interested in knowing whether the following conjecture is true or not: For every $d \geq 1$ there exist constants $\delta,M_0 > 0$ such that the following holds for all $M \geq M_0$. ...
92 views

Counting xyz-graphs in $\mathbb{Z}_n^3$

This is a followup question to: Lower bound on the largest restrained cubic subset How many distinct xyz-graphs exist in $\mathbb{Z}_n^3$? We denote this number as $C(n)$ This question may be seen ...
126 views

Lower bound on the largest restrained cubic subset

Consider an $n \times n \times n$ cube. I would like to consider subsets of points in the cube with the two following constraints: Each row in the cube (in any of the three directions) has exactly 2 ...
95 views

Detecting bridges in Hypergraph S-t Reachability

Is there a fast algorithm to detect possible bridge arcs in hyperpaths from set $S$ of nodes to node $t$ in a hypergraph $G$. That is, given a hypergraph $G$, source nodes $S$, and target node $t$, ...
214 views

Reduction from independent set in hypergraphs to independent set in graphs

Let me introduce my notations. IS-H : Input : an hypergraph $G=(V,H)$, an integer $k$ Question : is there a (weak) independent set of size $k$, i.e. a set $S \subseteq V$ such that $|S| \ge k$ and ...
93 views

What is the recognition complexity of k-uniform k-partite hypergraphs? [duplicate]

We can easily recognize bipartite graphs, but I surprisingly couldn't find anything on the recognition complexity of 3-uniform tripartite hypergraphs, though I'm sure this has been studied. It's also ...
263 views

Complexity of testing if a hypergraph has generalized hypertreewidth $2$

A hypergraph $H = (V, E)$ consists of a set of vertices $V$ and a set $E$ of hyperedges, i.e., subsets of $V$. The generalized hypertreewidth (GHW) parameter is a measure of the cyclicity of a ...
180 views

Complexity of #SAT for monotone DNF formulae whose hypergraph is a hypertree

A monotone DNF on variables $x_1, \ldots, x_n$ is a disjunction of clauses, each clause being a conjunction of some of the $x_1, \ldots, x_n$. The #SAT problem asks, given a monotone DNF $\Phi$, how ...
528 views

Is there an approximation algorithm for MAX k DOUBLE SET COVER?

Given a set system $(X,\mathcal S)$, let us say that a subset $\mathcal C\subseteq \mathcal S$ doubly covers a vertex $x$ in $X$ if $x$ is contained in at least two sets of $\mathcal C$. Let us define ...
290 views

NP-hardness of coloring uniform hypergraphs

Since a $2$-uniform hypergraphs are just graphs. The problem of deciding if $2$-uniform is $k$-colorable for $k=1,2$ is easy, and NP-hard for $k \geq 3$ colors. This is well know and I have seen ...
1k views

Hardness of 3-dimensional matching variant

I am thinking about a variant of 3-dimensional matching. In normal 3d matching, we have three sets of vertices $X$, $Y$ and $Z$, and a set of edges $E \subseteq X \times Y \times Z$. We want to choose ...
207 views

Intersection models for weakly chordal graphs?

Due to the apparent unpopularity of my previous posts, I'd like to post a question about graph theory which seems to be a popular topic here :) Among the many known classes of perfect graphs, there ...
820 views

Which properties of planar graphs generalize to higher dimension / hypergraphs?

A planar graph is a graph which can be embedded in the plane, without having crossing edges. Let $G=(X,E)$ be a $k$-uniform-hypergraph, i.e. an hypergraph such that all its hyperedges have size k. ...
274 views

Best approximation for a HYPERGRAPH-MAXDICUT problem

Consider a $(c^a,(c+d)^a,1)$-regular directed hypergraph $\mathcal{H}(a)$ on $n^a$ vertices with fixed $n\geq c+d+1$, fixed $c\geq 2$, fixed $d\geq 0$ and variable parameter $a\geq 1$ (meaning every ...
1k views

hardness of approximating the chromatic number in graphs with bounded degree

I am looking for hardness results on vertex coloring of graphs with bounded degree. Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor ...
3k views

Recognizing line graphs of hypergraphs

The line graph of a hypergraph $H$ is the (simple) graph $G$ having edges of $H$ as vertices with two edges of $H$ are adjacent in $G$ if they have nonempty intersection. A hypergraph is an $r$-...
281 views

k-uniform k-partite hypergraph matching in polynomial time

I have what seems like an elementary question, but google didn't throw up any answers for it. I would appreciate any pointers users here may provide. Please note that I have also asked this question ...
645 views

What are the root difficulties in going from graphs to hypergraphs?

There are many examples in combinatorics and computer science where we can analyze a graph-theoretic problem but for the problem's hypergraph analog, our tools are lacking. Why do you think problems ...
679 views