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

    Identifiers

    0 references
    0 references
    0 references
    0 references