# Complexity of calculating independence number of a hypergraph

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!

• it would be helpful to describe or ref the exact defn of hypergraph independent set (eg what pg in the dissertation etc) – vzn Mar 25 '14 at 20:17
• I added definitions. Thanks for the comment. – Joe Mitchell Mar 25 '14 at 20:35
• 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".... – vzn Mar 25 '14 at 21:42
• 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. – baffld Mar 25 '14 at 22:01
• "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". – David Richerby Mar 26 '14 at 0:23