On feasible sets of mixed hypergraphs (Q1883629)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On feasible sets of mixed hypergraphs |
scientific article |
Statements
On feasible sets of mixed hypergraphs (English)
0 references
13 October 2004
0 references
Summary: A mixed hypergraph \(H\) is a triple \((V,{\mathcal C},{\mathcal D})\) where \(V\) is the vertex set and \({\mathcal C}\) and \({\mathcal D}\) are families of subsets of \(V\), called \({\mathcal C}\)-edges and \({\mathcal D}\)-edges. A vertex coloring of \(H\) is proper if each \({\mathcal C}\)-edge contains two vertices with the same color and each \({\mathcal D}\)-edge contains two vertices with different colors. The spectrum of \(H\) is a vector \((r_1,\dots,r_m)\) such that there exist exactly \(r_i\) different colorings using exactly \(i\) colors, \(r_m\geq 1\) and there is no coloring using more than \(m\) colors. The feasible set of \(H\) is the set of all \(i\)'s such that \(r_i\neq 0\). We consider a mixed hypergraph with \(O (\sum_i\log r_i)\) vertices whose spectrum is equal to \((r_1,\dots,r_m)\) for each vector of non-negative integers with \(r_1=0\). We further prove that for any fixed finite sets of positive integers \(A_1\subset A_2\) \((1\notin A_2)\), it is NP-hard to decide whether the feasible set of a given mixed hypergraph is equal to \(A_2\) even if it is promised that it is either \(A_1\) or \(A_2\). This fact has several interesting corollaries, e.g., that deciding whether a feasible set of a mixed hypergraph is gap-free is both NP-hard and coNP-hard.
0 references
mixed hypergraph
0 references
coloring
0 references
feasible set
0 references