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.
- 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 ...
- 18.1k
5
votes
Complexity of testing if a hypergraph has generalized hypertreewidth $2$
We do not know (to best of my knowledge).
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 ...
- 1,642
4
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 ...
- 9,595
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 ...
- 2,164
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 ...
- 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 ...
- 14.3k
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 ...
- 1,429
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/...
- 2,164
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 ...
- 50.9k
2
votes
Accepted
Balanced set coloring
I think this question is closely related to the term discrepancy.
Here is the defintion.
Given a universe $U$ a collection of sets $\mathcal{A}=\{S_i\}$ and a function $\varphi:U\to\{-1,1\}$. For $S\...
- 136
2
votes
Accepted
Which hypergraphs can be simplified by alternatively removing a hyperedge and an isolated vertex?
It is NP-complete to decide if a hypergraph admits an elimination sequence.
The reason is that it can be seen to be equivalent to the following problem: given $n$ subsets of $\{1,2,\dots, n\}$ (...
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 \}$
...
- 22.6k
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 ...
- 3,256
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 ...
- 8,916
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 ...
- 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 ...
- 2,758
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).
...
- 225
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$ ...
- 18.9k
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)...
- 2,164
Only top scored, non community-wiki answers of a minimum length are eligible