On the time complexity of finding independent sets in hypergraphs

Question

I am interested in the complexity of the following problems:

(a) Finding an independent set of a fixed size in an arbitrary hypergraph

(b) Finding an independent set of maximum size in an arbitrary hypergraph

It is well known that the analogues of (a) and (b) (say (a') and (b')) for graphs are NP-complete and NP-hard, respectively. However, I am having trouble finding references for the complexity of (a) and (b). In fact, all of the papers I've been able to find on these two problems (for hypergraphs) just cite the fact that (a') and (b') are NP-complete and NP-hard, as if these results trivially generalize to (a) and (b). Is this actually the case? If not, can anyone provide references that prove the complexity of (a) and (b)?

Answer 1

The ubiquitous principle is that a generalized problem is at least as hard to the original problem. This rather trivial principle is applied as truism in most if not all papers.

---

Here is a specific version of that principle for the case of time-complexity.

Lemma. Let $A,B, C$ be three languages such that $A= B\cap C$ and $A\not=C$. ($C$ is considered as a generalization of $A$.) It takes polynomial time to determine whether $x\in B$. Then deciding $C$ is as least as hard as deciding $A$ modulo polynomial time. If $A$ is NP-complete and $C$ is in NP, then $C$ is NP-complete.

Proof. Let $\beta$ be a polynomial-time algorithm that decides $B$. Suppose we have an algorithm $\gamma$ that decides $C$. Let $\alpha$ be the following algorithm:

• Given input string $x$, run $\beta$ to determine if $x\in B$. If not, return no. If yes, run $\gamma$ to determine if $x\in C$. If not, return no. Return yes otherwise.

It is routine to check that $\alpha$ return yes if and only if the input is in $A$, i.e., $\alpha$ decides $A$. Since $\beta$ takes polynomial time, deciding $C$ is at least as hard as deciding $A$ modulo polynomial time.

It follows immediately that if $A$ is NP-complete and $C$ is in NP, then $C$ is NP-complete.

---

Let

• $A=\{\langle G,s\rangle \mid \text{ there is an independent set of size }s\text{ in an ordinary graph G}\}$. (I use the phrase "ordinary graph" or simply "graph" to contrast with "hypergraph". "General graph" sounds more like hypergraph. Indeed, hypergraph is a generalization of an ordinary graph.)
• Let $B=\{\langle G\rangle\mid G \text{ is an ordinary graph}\}$.
• Let $C=\{\langle G, s\rangle \mid \text{ there is an independent set of size }s\text{ in a hypergraph G}\}$.

The lemma tells us that deciding $C$ is at least as hard as deciding $A$.

---

Exercise 1. Explain that deciding whether a graph is 3-colorable is at least as hard as deciding whether a given planar-graph is 3-colorable. (In fact, both problems are NP-complete.)

Exercise 2. Prove that it is NP-complete to determine whether there is independent set of given size in a given triangle hypergraph. A triangle hypergraph is defined as a hypergraph where each edge is a set of 3 vertices.

Answer 2

We known that maximum independent set (MIS) is NP-complete on general graphs. Because every graph is also a hypergraph, we have that MIS is also NP-complete on hypergraphs.