# Questions tagged [hypergraphs]

The tag has no usage guidance.

35 questions
Filter by
Sorted by
Tagged with
71 views

### Are there classes for that FO-model checking is FPT on hypergraphs?

For graphs, there are many classes that admit FPT-algorithms for model checking of first order logic, e.g. the class of nowhere dense graphs by Grohe et. al. Are there similar results for ($k$-uniform)...
• 41
135 views

### Which hypergraphs can be simplified by alternatively removing a hyperedge and an isolated vertex?

Let $H = (V, E)$ be a hypergraph, with $V$ the set of vertices and $E \subseteq 2^V$ the set of hyperedges. An elimination sequence on $H$ consists of alternatively removing hyperedges. Specifically, ...
• 7,455
1 vote
70 views

### Hardness of vertex colouring on hypergraphs with $O(\log n)$ edges

I'm interested to know whether there has been any work done on the problem in the title. For the problem to be meaningful, we would naturally need that the hyperedges must have large ($\omega(1)$) ...
• 331
138 views

• 14.1k
97 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 ...
• 223
130 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 ...
• 223
1 vote
113 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$, ...
• 338
1 vote
239 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 ...
• 137
136 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 ...
• 13.5k
279 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 ...
• 7,455
244 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 ...
• 7,455
981 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 ...
• 2,101
301 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 ...
219 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 ...
• 1,292
1k 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. ...
• 9,378
311 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 ...
2k 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 ...
• 271
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$-...
• 2,467
285 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 ...
• 779
733 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 ...
• 6,940
831 views

• 2,583
411 views

### Efficient algorithm for near-optimal edge-colourings of hypergraphs

Graph colouring problems are, already, hard enough for most people. Even so, I'm going to have to be difficult and ask a problem about hypergraph colouring. Question. What efficient algorithms are ...
• 8,821