13 votes
Accepted

NP-hardness of coloring uniform hypergraphs

$2$-coloring $s$-uniform hypergraphs is also called Set Splitting, problem [SP4] in Garey-Johnson book. The hardness proof is due to Lovasz in this paper.
vb le's user avatar
  • 4,828
6 votes
Accepted

Reduction of graph chromatic number to hypergraph 2-colorability

As the other answer points out, the reduction in the original paper seems to have a bug: $H$ will not be two-colorable unless $G$ is bipartite. I couldn't quite see how to prove the reduction in the ...
Sasho Nikolov's user avatar
5 votes

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

We do not know (to best of my knowledge).
Zoltan Miklos's user avatar
4 votes
Accepted

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

(Comment $\rightarrow$ Answer) Consider the following algorithms for a hypergraph $(U,\mathcal S)$, with $n=|U|$: For a set $X\subseteq \mathcal S$ of sets and a set $A \in X$, define $d_X(A)$ as ...
Yonatan N's user avatar
  • 1,642
4 votes
Accepted

When is hypertree width more useful than generalized hypertree width?

Every XP/FPT algorithm parametrized by htw also gives an XP/FPT algorithm parametrized by ghtw (provided that the decomposition is given in the input) since there is a linear relation between ghw and ...
holf's user avatar
  • 2,059
3 votes

Reduction of graph chromatic number to hypergraph 2-colorability

I don't think this is true as stated, since if $(u,v)$,$(u,w)$,$(v,w)$ is a triangle in $G$ then clearly there is no way to "two color" the corresponding hyper edges in $H$ no matter how many ...
mm8511's user avatar
  • 203
3 votes
Accepted

Almost regular subhypergraph of hypergraph with large minimal degree

Unfortunately the conjecture is wrong (for $d \geq 2$). Here is a counterexample for $d=2$. Suppose that the conjecture (in its graphical formulation) held for some $c,M_0 > 0$. Consider a ...
Yuval Filmus's user avatar
  • 14.2k
3 votes
Accepted

Lower bound on the largest restrained cubic subset

These subsets of grids, and your graph-theoretic interpretation of them, are studied in my paper The complexity of bendless three-dimensional orthogonal graph drawing. D. Eppstein. J. Graph ...
David Eppstein's user avatar
3 votes

Reduction from independent set in hypergraphs to independent set in graphs

From the standard machinery, we can quickly deduce that there is a quasilinear-time reduction from $\textrm{IS-H}$ to $\textrm{IS}$. (But see below if quasilinear isn't good enough for you.) Recall ...
Andrew Morgan's user avatar
3 votes
Accepted

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

A new paper from Wolfgang Fischl, Georg Gottlob, Reinhard Pichler states that it remains hard even for $k = 2$. I still haven't read it however, I am just providing the link: https://arxiv.org/abs/...
holf's user avatar
  • 2,059
3 votes
Accepted

Shortest path on a hypergraph with no leftovers

This answer doesn't answer the question about previous work, but it does show the problem is NP-complete. Lemma 1. Finding a shortest $s$-$t$ hyperpath (as defined in the post) in a given hypergraph ...
Neal Young's user avatar
  • 9,545
2 votes
Accepted

3-dimensional matching variant

No, the variant is in P: for each element $x_i \in X$ find the set $A_{x_i}$ of triples "reachable" from $x_i$: start with all triples containing $x_i$ $A_{x_i} = \{ (x, y, z) \mid x = x_i \}$ ...
Marzio De Biasi's user avatar
2 votes
Accepted

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

The problem is NP-hard for $k=3$ already. Indeed, testing if a graph is tripartite (i.e., there exists a partition $V_1 \sqcup V_2 \sqcup V_3$ of its vertex set $V$ such that each edge is between two ...
a3nm's user avatar
  • 8,234
2 votes

Lower bound on the largest restrained cubic subset

Consider the points in the cube as indexed by $(x,y,z) \in \mathbb{Z}_n^3$ and consider the point set $\{(x,y,z) : z = x + y\} \cup \{(x,y,z) : z = x + y + 1\}$. Here addition is done modulo $n$. This ...
daniello's user avatar
  • 3,236
2 votes
Accepted

Expander Graph from Hypergraph

This is not an answer but is too long for a comment: The graph you care about is called the line graph of the hypergraph. For usual graphs, it is well known that the line graph of an expander graph ...
Arnaud's user avatar
  • 824
1 vote

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

This answer addresses the NP-hardness of the SPANNING SYMMETRIC HYPERFOREST ROOT SET (SSHRS) problem (given an undirected hypergraph $G$ and a number $k$, is there a spanning hyperforest with root set ...
Mikhail Rudoy's user avatar
1 vote
Accepted

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

Consider that hamiltonian cycles of the bipartite graph are isomorphic (that is we can always permute the rows amongst themselves and the columns similarly to reach any other hamiltonian cycle). ...
Max Hopkins's user avatar
1 vote

Reduction from independent set in hypergraphs to independent set in graphs

I am not as convinced as @Andrew Morgan is that this is "fair standard fare", and would also welcome pointers to a citable reduction. In particular, I do not see how to maintain a linear blowup if $k$ ...
András Salamon's user avatar
1 vote
Accepted

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

Observe that the negation of a (monotone) CNF-formula F is a (monotone) DNF G which has the same hypergraph. Moreover #G = 2^n-#F where n is the number of variables of F. Thus, every known (structural)...
holf's user avatar
  • 2,059

Only top scored, non community-wiki answers of a minimum length are eligible