论文标题
列表的稀疏下限$ h $彩色
Sparsification Lower Bounds for List $H$-Coloring
论文作者
论文摘要
我们调查了列表$ h $颜色的问题，图形颜色的概括，询问输入图$ g $是否允许对无向图$ h $（可能带有loops）的同构，因此每个顶点$ v \ in v（g）$ in v（g）$ in列表$ l（v）$ l（v）\ subseteq v（h）$。 Feder，Hell和Huang [JGT 2003]指出，如果$ h $颜色列表是多项式时间解决的，那么如果$ h $是所谓的BI-ARC图，则可以解决。我们从多项式时间稀疏的角度研究了问题的NP完整案例：对于某些$ \ varepsilon> 0 $ 0 $，可以有效地将$ n $ vertex实例有效地降低为bitsize $ o（n^{2- \ varepsilon}）$的等效实例吗？我们证明，如果$ h $不是BI-ARC图，则列表$ h $ - 颜色不承认这样的稀疏算法，除非$ np \ subseteq conp/poly $。我们的证明将核心化下限的技术与对不是双arc图的图形结构的研究结合在一起。
We investigate the List $H$-Coloring problem, the generalization of graph coloring that asks whether an input graph $G$ admits a homomorphism to the undirected graph $H$ (possibly with loops), such that each vertex $v \in V(G)$ is mapped to a vertex on its list $L(v) \subseteq V(H)$. An important result by Feder, Hell, and Huang [JGT 2003] states that List $H$-Coloring is polynomial-time solvable if $H$ is a so-called bi-arc graph, and NP-complete otherwise. We investigate the NP-complete cases of the problem from the perspective of polynomial-time sparsification: can an $n$-vertex instance be efficiently reduced to an equivalent instance of bitsize $O(n^{2-\varepsilon})$ for some $\varepsilon > 0$? We prove that if $H$ is not a bi-arc graph, then List $H$-Coloring does not admit such a sparsification algorithm unless $NP \subseteq coNP/poly$. Our proofs combine techniques from kernelization lower bounds with a study of the structure of graphs $H$ which are not bi-arc graphs.
