<p>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.)</p>

<p>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))$.</p>

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

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

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

<hr>

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

<p>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 <a href="https://en.wikipedia.org/wiki/Tseytin_transformation" rel="nofollow noreferrer">Tseitin transformation</a>) 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}$.</p>

<p>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$.</p>

<ul>
<li><p>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.</p></li>
<li><p>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.</p></li>
<li><p>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 <em>e.g.</em> <a href="https://cstheory.stackexchange.com/questions/21386/circuit-complexity-of-majority-function">the answers here</a>, 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$.</p></li>
</ul>

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

CC BY-SA 3.0
2016-07-17T15:24:35.453Z
2016-07-17T15:24:35.453Z
2017-04-13T12:32:28.167Z
Andrew Morgan
<p>I am not as convinced as @Andrew Morgan is that this is "fair standard fare", and would also welcome pointers to a citable reduction.
<strike>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\}$.</strike>
(<em>Edit:</em> 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.</p>

<p>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$".</p>

<p>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$.
<em>Edit:</em> 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.</p>

<p>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$.
<em>Edit:</em> $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.</p>

<p>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$.</p>

<ul>
<li>Paul E. Dunne, <em>The Complexity of Boolean Networks</em>, Academic Press, 1988. (<a href="https://cgi.csc.liv.ac.uk/~ped/all.pdf.gz" rel="nofollow">preprint</a>)</li>
<li>Martin Kochol, <em>Efficient Monotone Circuits for Threshold Functions</em>, IPL <strong>32</strong>, 1989, 121–122.
doi:<a href="http://dx.doi.org/10.1016/0020-0190(89)90011-2" rel="nofollow">10.1016/0020-0190(89)90011-2</a></li>
<li>Paul E. Dunne, <em>Comment on Kochol's Paper ``Efficient Monotone Circuits for Threshold Functions''</em>, IPL <strong>34</strong>, 1990, 221–222.
doi:<a href="http://dx.doi.org/10.1016/0020-0190(90)90125-H" rel="nofollow">10.1016/0020-0190(90)90125-H</a></li>
</ul>

CC BY-SA 3.0
2016-07-16T20:21:41.227Z
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.
Andrew Morgan
CC BY-SA 3.0
2016-07-17T03:15:28.677Z
Would that not improve the Dunne/Kochoi upper bounds for threshold gates, though?  The small details seem to matter unfortunately.
András Salamon
CC BY-SA 3.0
2016-07-17T03:41:21.733Z
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.
Andrew Morgan
CC BY-SA 3.0
2016-07-17T12:30:18.917Z
I'm sorry, but I don't see any way to avoid a multiplicative dependence on both $k$ or $\log k$ and $n$ in the circuit size.  Do you have more details of the circuit you are thinking of?  In the applications I am thinking of, $k = \Theta(n)$ so a truly linear reduction would be quite nice.
András Salamon
CC BY-SA 3.0
2016-07-17T15:26:55.483Z
I wrote it up as a new answer. But more briefly see the answers [here](http://cstheory.stackexchange.com/questions/21386/circuit-complexity-of-majority-function).
Andrew Morgan
CC BY-SA 3.0
2016-07-18T12:18:24.980Z
Thanks, the pointer to Muller and Preparata 1975 (via Wegener's book) is what I was missing.  http://dx.doi.org/10.1145/321879.321882
András Salamon
CC BY-SA 3.0
2016-07-16T19:24:46.490Z
2016-07-18T11:00:57.817Z
2016-07-18T11:00:57.817Z
András Salamon
<p>Let me introduce my notations.</p>

<p>IS-H :</p>

<ul>
<li>Input : an hypergraph $G=(V,H)$, an integer $k$</li>
<li>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$ ?</li>
</ul>

<p>I denote IS the same problems in graphs.</p>

<p>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).</p>

<p>Do you know if such a reduction is made explicit somewhere ?
Thank you in advance</p>

CC BY-SA 3.0
2016-07-11T11:12:48.170Z
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.
Alex Meiburg
CC BY-SA 3.0
2016-07-11T15:24:12.593Z
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.
Andrew Morgan
CC BY-SA 3.0
2016-07-11T15:25:08.077Z
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.
Andrew Morgan
<graph-theory><graph-algorithms><reductions><hypergraphs><independent-set>
Reduction from independent set in hypergraphs to independent set in graphs
user32018
# Reduction from independent set in hypergraphs to independent set in graphs

(Asked by: username_0 on 2016-07-11)

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

**Tags:** graph-theory, graph-algorithms, reductions, hypergraphs, independent-set
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_2 on 2016-07-17. Score: 3

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](https://en.wikipedia.org/wiki/Tseytin_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](https://cstheory.stackexchange.com/questions/21386/circuit-complexity-of-majority-function), 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 by username_3 on 2016-07-16. Score: 1

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](https://cgi.csc.liv.ac.uk/~ped/all.pdf.gz))
* Martin Kochol, *Efficient Monotone Circuits for Threshold Functions*, IPL **32**, 1989, 121–122.
  doi:[10.1016/0020-0190(89)90011-2](http://dx.doi.org/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](http://dx.doi.org/10.1016/0020-0190(90)90125-H)

> **Comments:**
> **username_2**: 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.  
> **username_3**: Would that not improve the Dunne/Kochoi upper bounds for threshold gates, though?  The small details seem to matter unfortunately.  
> **username_2**: 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.  
> **username_3**: I'm sorry, but I don't see any way to avoid a multiplicative dependence on both $k$ or $\log k$ and $n$ in the circuit size.  Do you have more details of the circuit you are thinking of?  In the applications I am thinking of, $k = \Theta(n)$ so a truly linear reduction would be quite nice.  
> **username_2**: I wrote it up as a new answer. But more briefly see the answers [here](http://cstheory.stackexchange.com/questions/21386/circuit-complexity-of-majority-function).  
> **username_3**: Thanks, the pointer to Muller and Preparata 1975 (via Wegener's book) is what I was missing.  http://dx.doi.org/10.1145/321879.321882  

---

