4
$\begingroup$

Let $G$ be a "hypergraph", a collection of vertices $V=\{v_1,v_2,\ldots,v_n\}$ and a collection of "hyperedges" $E=\{e_1,e_2,\ldots,e_m\}$, where $e_i\subseteq V$ and unlike normal edges, an edge may contain more than two vertices.

An "independent set" (http://en.wikipedia.org/wiki/Independent_set_(graph_theory)) is a collection of vertices, $U$, that does not fully contain any of the hyperedges: $e_i\not\subseteq U$. The "independence number" or "maximum independent set size" is the size of the largest independent set in the graph $G$.

I know that finding if there is an independent set of size $k\in\mathbb{N}$ in some normal graph $G$ is NP-Complete. If I am not mistaken, this holds for hypergraphs as well. However calculating the independence number is not proven to be NP. Even approximating it is not proven in NP.

First, is there a more specific complexity class for calculating the independence number than NP-Hard?

Second, how much harder is it for a hypergraph? Again, is there a complexity class more specific?

For related questions, a recent dissertation has been helpful to me: https://escholarship.org/uc/item/79t9b162.

Thanks!

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ it would be helpful to describe or ref the exact defn of hypergraph independent set (eg what pg in the dissertation etc) $\endgroup$ – vzn Mar 25 '14 at 20:17
  • $\begingroup$ I added definitions. Thanks for the comment. $\endgroup$ – Joe Mitchell Mar 25 '14 at 20:35
  • 1
    $\begingroup$ there seems to be recent/active research eg by Saket but its more about approximability hardness results. when you ask for "more specific class" do you mean, is it known to be harder than NP-Hard? saket's are indeed "more specific results" but not nec in terms of a "more specific class".... $\endgroup$ – vzn Mar 25 '14 at 21:42
  • 1
    $\begingroup$ FWIW, if a bipartite graph can be used to represent hyper graphs, then I agree the reduction is not as trivial as simply converting the hyper graph $\langle H \rangle$ to a bipartite graph $\langle G \rangle$ and running some algo that finds max independent set on $\langle G \rangle$. There would be some more sophisticated gadgetry in the reduction if this route were to be taken. At any rate, if you need a production-level solution, then best of luck to you. $\endgroup$ – baffld Mar 25 '14 at 22:01
  • 1
    $\begingroup$ "However calculating the independence number is not proven to be NP." Calculating any number is not in NP because NP is a class of decision problems: problems where the answer is either "yes" or "no". $\endgroup$ – David Richerby Mar 26 '14 at 0:23
2
$\begingroup$

did not find a proof of complexity class harder than "NP hard" for this problem (ie the presumably more complex hypergraph version of the problem does not seem to have been proven harder than the graph version) however did find the following. Saket has recent research in the area. results in complexity theory in active areas of research tend to be highly specialized and in the form "for limited hypergraph types [x], the following improved complexity bound [y] is shown." (ie more as approximability results, & more specialized than what you request but it can be mined for nearest desirable results/refs.)

basically hypergraphs while an old mathematical concept are a more recent area of complexity theory research and there is a large active/ongoing research program of determining complexity of operations around them and how those complexities relate to corresponding graph operation complexities, and translating theorems and knowledge about graphs into their hypergraph analogs.

Improve this answer
$\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.