1
$\begingroup$

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)?

$\endgroup$
  • 1
    $\begingroup$ Do you have any constraints on the hypergraphs? If not, then since any general graph is also a hypergraph, and so MIS for hypergraphs is trivially just as hard. Think about it this way - if you have an algorithm for MIS on general hypergraphs, it must also be able to solve MIS on any general graphs (and hence the reduction is trivial). $\endgroup$ – BearAqua May 8 '19 at 3:17
  • $\begingroup$ So what you're saying is that if MIS on general hypergraphs were "better" (can't think of the right word here) than NP-hard, then MIS on general graphs must also be "better" than NP-hard, which can't be the case? $\endgroup$ – user95224 May 8 '19 at 3:27
  • $\begingroup$ Does your reasoning imply that MIS on a general hypergraph is NP-hard, or merely that it is "at best" NP-hard? $\endgroup$ – user95224 May 8 '19 at 5:02
  • $\begingroup$ No. I'm saying that MIS on hypergraphs is "at least" NPH, since MIS on general graphs is already NPH. $\endgroup$ – BearAqua May 8 '19 at 12:31
  • $\begingroup$ Understood, thanks. $\endgroup$ – user95224 May 9 '19 at 1:12
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.