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

  • $\begingroup$ Why are people downvoting (esp without comment)? This seems like a good question. What is a known bound on the reduction rate from ISH to IS? I'm curious as well. $\endgroup$ – Alex Meiburg Jul 11 '16 at 11:12
  • 1
    $\begingroup$ The standard proofs of $\mathsf{NP}$-hardness are already completely explicit. The reduction from 3-SAT to IS has only linear blowup, and it's well-known that there are reductions from $\mathsf{NTIME}[t(n)]$ to 3-SAT that result in formulas of size $\tilde{O}(t(n))$. Since IS-H can be solved nondeterministically in quasilinear time, it follows that the standard machinery already gives a reduction from IS-H to IS with only quasilinear blowup. $\endgroup$ – Andrew Morgan Jul 11 '16 at 15:24
  • 1
    $\begingroup$ In fact, if you specialize these pieces to IS-H, you can actually get a simple, explicit reduction from IS-H to IS with just linear blowup. All of this is fairly standard fare, and not even a particularly creative application of it, which might explain the poor reception. $\endgroup$ – Andrew Morgan Jul 11 '16 at 15:25

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.


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
  • $\begingroup$ Wouldn't it suffice to think of computing the threshold check via a linear-size $\mathrm{NC}^1$ formula (it's a symmetric function) and then doing the usual Tseitin transform to get a 3-CNF out of it? This seems to work for any $k$, and is pretty straightforward. I'll admit that I did forget to consider this part of the reduction when I wrote my second comment above, and that makes a linear-blowup reduction not quite so easy. $\endgroup$ – Andrew Morgan Jul 16 '16 at 20:21
  • $\begingroup$ Would that not improve the Dunne/Kochoi upper bounds for threshold gates, though? The small details seem to matter unfortunately. $\endgroup$ – András Salamon Jul 17 '16 at 3:15
  • $\begingroup$ Their results are concerned with the monotone circuit complexity of threshold functions. We don't need the circuit to be monotone; any efficiently computable, linear size, bounded fan-in circuit will suffice. $\endgroup$ – Andrew Morgan Jul 17 '16 at 3:41
  • 1
    $\begingroup$ I wrote it up as a new answer. But more briefly see the answers here. $\endgroup$ – Andrew Morgan Jul 17 '16 at 15:26
  • 1
    $\begingroup$ Thanks, the pointer to Muller and Preparata 1975 (via Wegener's book) is what I was missing. dx.doi.org/10.1145/321879.321882 $\endgroup$ – András Salamon Jul 18 '16 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.