On Feasible Sets of Mixed Hypergraphs
On Feasible Sets of Mixed Hypergraphs
复制标题
DOI：
10.37236/1772
复制
发表时间：
2004-03
期刊：
影响因子：
--
通讯作者：
D. Král
中科院分区：
文献类型：
--
作者：
D. Král
混合超图H是一个三元组（V，{\cal C}，{\cal D}），其中V是顶点集，C和D是V的子集族，称为C边和D边。一个顶点着色为H是适当的，如果每个C-边包含两个相同颜色的顶点，而每个D-边包含两个不同颜色的顶点. $H$的光谱是一个向量$（r_1，\ldots，r_m）$，使得存在$r_i$种不同的着色，使用的颜色正好是$i$种，$r_m\ge 1$，并且不存在使用超过$m$种颜色的着色。$H$的可行集是所有$i$的集合，使得$r_i\ne 0$。我们构造了一个顶点数为O（\sum_i\log r_i）$的混合超图，对于每个非负整数向量，$r_1=0$，其谱等于$（r_1，\ldots，r_m）$.进一步证明了对任意固定的有限正整数集A_1\子集A_2$（A_2$中的1\notin A_2$），即使保证混合超图的可行集是A_1 $或A_2 $，判定其可行集是否等于A_2 $也是NP-困难的.这一事实有几个有趣的推论，例如，证明了判定混合超图的可行集是否是无间隙集是NP-难的，也是CoNP-难的。
A mixed hypergraph $H$ is a triple $(V,{\cal C},{\cal D})$ where $V$ is the vertex set and ${\cal C}$ and ${\cal D}$ are families of subsets of $V$, called ${\cal C}$-edges and ${\cal D}$-edges. A vertex coloring of $H$ is proper if each ${\cal C}$-edge contains two vertices with the same color and each ${\cal D}$-edge contains two vertices with different colors. The spectrum of $H$ is a vector $(r_1,\ldots,r_m)$ such that there exist exactly $r_i$ different colorings using exactly $i$ colors, $r_m\ge 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\ne 0$. We construct a mixed hypergraph with $O(\sum_i\log r_i)$ vertices whose spectrum is equal to $(r_1,\ldots,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.