# Tag Info

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.
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 ...

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

We do not know (to best of my knowledge).
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 ...
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 ...
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 ...

### 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 ...
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 ...

### 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 ...
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/...
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 ...