patternMinor
Complexity of calculating independence number of a hypergraph
Viewed 0 times
independencenumberhypergraphcalculatingcomplexity
Problem
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!
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!
Solution
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.
-
Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs Saket (Dec 2013)
This work revisits the PCP Verifiers used in the works of H˚astad [H˚as01], Guruswami et al. [GHS02],
Holmerin [Hol02] and Guruswami [Gur00] for satisfiable MAX-E3-SAT and MAX-Ek-SET-SPLITTING,
and independent set in 2-colorable 4-uniform hypergraphs. We provide simpler and more efficient PCP
Verifiers to prove ... improved hardness results ...
-
Hardness of Maximum Independent Set in Structured Hypergraphs Saket powerpoint slides overview
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.
-
Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs Saket (Dec 2013)
This work revisits the PCP Verifiers used in the works of H˚astad [H˚as01], Guruswami et al. [GHS02],
Holmerin [Hol02] and Guruswami [Gur00] for satisfiable MAX-E3-SAT and MAX-Ek-SET-SPLITTING,
and independent set in 2-colorable 4-uniform hypergraphs. We provide simpler and more efficient PCP
Verifiers to prove ... improved hardness results ...
-
Hardness of Maximum Independent Set in Structured Hypergraphs Saket powerpoint slides overview
Context
StackExchange Computer Science Q#23044, answer score: 2
Revisions (0)
No revisions yet.