Reduction from independent set in hypergraphs to independent set in graphs 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
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.