Reduction from independent set in hypergraphs to independent set in graphs

Question

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 for all $h\in H$, $h \nsubseteq S$ ?

I denote IS the same problems in graphs.

I know that $IS-H \le_{karp} IS$ as $IS-H \in NP$ and $IS$ is $NP-hard$, but I need an explicit reduction to compute an explicit bound on the size of the obtained instance of $IS$. I have such a reduction in mind but I would prefer to cite an existing one (any "natural" reduction is ok for me, as I don't need to tune the constant in the size of the obtained instance).

Do you know if such a reduction is made explicit somewhere ? Thank you in advance

Answer 1

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 that $\textrm{3-SAT}$ is hard for $\mathsf{NTIME}[t(n)]$ under reductions that run in time $\tilde{O}(t(n))$, and in particular the resulting 3-CNF formula has size $\tilde{O}(t(n))$.

It's fairly straightforward to check that $\textrm{IS-H}$ can be solved in $\mathsf{NTIME}[\tilde{O}(n)]$ in any reasonable model of computation. (The naive algorithm has some dependence on $n \cdot k$, but this can be reduced with some sorting and binary search.) It follows that there is a reduction from $\textrm{IS-H}$ to $\textrm{3-SAT}$ which has only quasilinear blowup.

Additionally, the usual reduction from $\textrm{3-SAT}$ to $\textrm{IS}$, where 2-cliques are made for each variable and 3-cliques are made for each clause and some edges are added between clause gadgets and the clause's constituent variables' gadgets, has only linear blowup (a 3-CNF on $n$ variables and $m$ clauses gets mapped to an $\textrm{IS}$ instance with $2n+3m$ vertices and $2n+6m$ edges.

Composing these two reductions gives an overall quasilinear-blowup reduction from $\textrm{IS-H}$ to $\textrm{IS}$.

---

If a quasilinear-blowup reduction isn't good enough for you, we can work a little harder to get a linear-blowup reduction.

The idea is to replace the reduction from $\textrm{IS-H}$ to $\textrm{3-SAT}$ by a more efficient reduction. To do this, we'll reduce $\textrm{IS-H}$ to a version of $\textrm{Circuit-SAT}$ which takes as input circuits in which all gates have fan-in 2. This reduction will have linear blowup. From here, we can use the standard reduction from fan-in 2 $\textrm{Circuit-SAT}$ to $\textrm{3-SAT}$ (using the Tseitin transformation) which has only linear blowup. Composing these with the linear-blowup reduction from $\textrm{3-SAT}$ to $\textrm{IS}$ then completes a linear-blowup reduction from $\textrm{IS-H}$ to $\textrm{IS}$.

The reduction from $\textrm{IS-H}$ to $\textrm{Circuit-SAT}$ proceeds as follows. Let the input hypergraph be $(V,E)$, where we view $E \subseteq 2^V$ which doesn't contain the empty set. Let the input threshold be $k$.

• We make variables $x_v$ for every vertex $v \in V$. We think of assignments to the variables as corresponding to subsets $S$ of the variables, where $v \in S$ if and only if $x_v \gets \texttt{True}$ in the assignment.

• For each edge $e$, we construct a fan-in 2 formula computing $\bigvee_{v\in e} \overline{x_v}$, to rule out sets $S$ which are not independent sets.

• Finally, we just need to translate the constraint $|S| \ge k$. To do this, we just need to give a linear-size, fan-in 2 circuit $\phi$ which takes as input $n$ bits and decides whether the number of bits set to $\texttt{True}$ is at least $k$. This can be done efficiently; see e.g. the answers here, but briefly the idea is just to efficiently compute the binary representation of the number of bits set to $\texttt{True}$, whence any symmetric function can be computed by a circuit of size linear in $n$.

It's easy to check that this is indeed a reduction from $\textrm{IS-H}$ to $\textrm{Circuit-SAT}$ in which the output has fan-in 2 gates and size only linear in the $\textrm{IS-H}$ instance. Moreover, the reduction results in a circuit of size $O(|V| + |E|)$ (where $|E|$ denotes $\sum_{e\in E}|e|$), and so we are done.

Answer 2

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$ depends on $n$, because encoding that the independent set is large enough with linear blowup seems to require a simulation of any threshold gate by a linear-size circuit over $\{\land,\lor,\lnot\}$. (Edit: The most intricate part of the reduction is how to enforce the size-$k$ constraint; as pointed out in another answer, a threshold gate can be simulated by a linear-size circuit that adds up the number of set bits and compares the resulting binary number to $k$.) Here is a reduction along the lines hinted at in the comments.

For convenience let $n=|V|$, $m=|H|$, and assume that $k \le (n+1)/2$. First create the direct encoding of $G$ as an intermediate SAT instance $I$, with variables $V$ and clauses $H'$. Variable $u\in V$ in $I$ is set in an assignment iff $u\in S$. Each edge $h\in H$ is mapped to a clause $\{\lnot u\mid u\in h\}\in H'$, encoding the constraint "at least one of the vertices in $h$ should not be in $S$".

To ensure that a solution of SAT instance $I$ sets at least $k$ variables to true, some additional clauses need to be added to $H'$. The straightforward way to do this is by adding $f(n,k)=\binom{n}{n-k+1}$ clauses, each containing $n-k+1$ positive literals. Alas, this requires between $(n/(k-1))^{k-1}$ and $(en/(k-1))^{k-1}$ new clauses. This blows up the final graph by a factor that is a polynomial with degree depending on $k$, and when $k$ grows with $n$, even very slowly, the blowup is superpolynomial. An improvement is to use a monotone threshold gate simulated by $f(n,k)=O(n\log k)$ clauses (each of size 3) to encode the constraint that at least $k$ of the variables must be set. This works for sufficiently large $k$. However, if $k$ is not sufficiently large to dominate the constants (which can be galactic), then we use Dunne's earlier construction instead (Theorem 3.14 in his book), with $f(n,k)=kn+O(n^{1-1/k})$ clauses. Either way, $m'=|H'|= m+f(n,k)$ depends only quite weakly on $k$. Edit: In fact, the dependence on $k$ can be eliminated altogether by using a non-monotone circuit that counts the number of set input bits, and compares the resulting $\log n$ bit binary number to the binary representation of $k$; such a circuit can be simulated by $O(n)$ clauses of size 3. Hence $H'$ will contain the $m$ original clauses together with $O(n)$ new clauses of size 3.

Now create the graph $G'$ with vertices $\{(u,g)\mid u\in g,g\in H'\}$ and an edge between $(u,g)$ and $(v,h)$ whenever $g=h$ or $u=\lnot v$. Edit: $G'$ has as many vertices as the number of vertices appearing in the edges of $G$ (i.e. counting a vertex every time it appears in an edge), together with $O(n)$ additional vertices.

I then claim that $G'$ has an independent set of size at least $m'$ iff $I$ has a solution iff $G$ contains an independent set of size at least $k$.

• Paul E. Dunne, The Complexity of Boolean Networks, Academic Press, 1988. (preprint)
• Martin Kochol, Efficient Monotone Circuits for Threshold Functions, IPL 32, 1989, 121–122. doi:10.1016/0020-0190(89)90011-2
• Paul E. Dunne, Comment on Kochol's Paper ``Efficient Monotone Circuits for Threshold Functions'', IPL 34, 1990, 221–222. doi:10.1016/0020-0190(90)90125-H