论文标题
计算有限的树和平面图上的方形着色
Computing Square Colorings on Bounded-Treewidth and Planar Graphs
论文作者
论文摘要
图形$ g $的正方形着色是$ g $ $ g $的Square $ g^2 $的着色，即$ g $的顶点的着色，以使任何两个在距离$ 2 $ in $ g $中的顶点最多2 $ in $ g $获得不同的颜色。我们研究了找到具有给定数量的$ Q $颜色的正方形着色的复杂性。我们表明，问题是通过在运行时呈现算法$ n^{2^{\ propatatorName {tw} + 4} + 4} + 4} + o（1）} $，以最多在$ $ \ perepatateRateOrnOrnArnAme {tw} $中，可以通过运行时间$ n^{2^{2^{\ operatorName {\ operatorName {\ operatorname {tw} + 4} + o（tw} $）。在运行时间内的某种不寻常的指数$ 2^{\ promatorName {tw}} $实质上是最佳的：我们证明，对于任何$ε> 0 $，都没有运行时间$ f（\ propatorNAME {tw} tw}）n^{（2-ε）^{（2-ε）^{\ operatorneys的算法，ntw} 我们还表明，方形着色问题是平面图上的NP-固定数字$ q \ ge 4 $的颜色。我们的主要算法结果表明，可以在平面图上的问题（当颜色数量$ q $是输入的一部分时）可以在次指定时间$ 2^{o（n^{2/3} \ log n）} $中求解。结果来自两种算法的组合。如果颜色的数字$ q $很小（$ \ le n^{1/3} $），那么我们可以利用图表正方形上的树宽限制，以解决问题$ 2^{o（\ sqrt {qn} \ log log n）} $。如果颜色的数量很大（$ \ ge n^{1/3} $），则基于突出分解的算法，并基于我们为有界树的结果而构建的算法可以在时间上解决问题$ 2^{o（n \ log n/q）} $。
A square coloring of a graph $G$ is a coloring of the square $G^2$ of $G$, that is, a coloring of the vertices of $G$ such that any two vertices that are at distance at most $2$ in $G$ receive different colors. We investigate the complexity of finding a square coloring with a given number of $q$ colors. We show that the problem is polynomial-time solvable on graphs of bounded treewidth by presenting an algorithm with running time $n^{2^{\operatorname{tw} + 4}+O(1)}$ for graphs of treewidth at most $\operatorname{tw}$. The somewhat unusual exponent $2^{\operatorname{tw}}$ in the running time is essentially optimal: we show that for any $ε>0$, there is no algorithm with running time $f(\operatorname{tw})n^{(2-ε)^{\operatorname{tw}}}$ unless the Exponential-Time Hypothesis (ETH) fails. We also show that the square coloring problem is NP-hard on planar graphs for any fixed number $q \ge 4$ of colors. Our main algorithmic result is showing that the problem (when the number of colors $q$ is part of the input) can be solved in subexponential time $2^{O(n^{2/3}\log n)}$ on planar graphs. The result follows from the combination of two algorithms. If the number $q$ of colors is small ($\le n^{1/3}$), then we can exploit a treewidth bound on the square of the graph to solve the problem in time $2^{O(\sqrt{qn}\log n)}$. If the number of colors is large ($\ge n^{1/3}$), then an algorithm based on protrusion decompositions and building on our result for the bounded-treewidth case solves the problem in time $2^{O(n\log n/q)}$.
