# Tag Info

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

### 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 ...
• 1,642
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 ...
• 10.1k
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,174

### 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
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.4k
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,174

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

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,174

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