(2023) Computing Square Colorings on BoundedTreewidth and Planar Graphs.

Text
soda2023paper105.pdf Download (938kB)  Preview 
Abstract
A {\em 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 polynomialtime solvable on graphs of bounded treewidth by presenting an algorithm with running time $n^{2^{\ttw + 4}+O(1)}$ for graphs of treewidth at most $\ttw$. The somewhat unusual exponent $2^\ttw$ in the running time is essentially optimal: we show that for any $\epsilon>0$, there is no algorithm with running time $f(\ttw)n^{(2\epsilon)^\ttw}$ unless the ExponentialTime Hypothesis (ETH) fails. We also show that the square coloring problem is NPhard 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 boundedtreewidth case solves the problem in time $2^{O(n\log n/q)}$.
Item Type:  Conference or Workshop Item (A Paper) (Paper) 

Divisions:  Dániel Marx (DM) 
Conference:  SODA ACM/SIAM Symposium on Discrete Algorithms 
Depositing User:  Dániel Marx 
Date Deposited:  12 Oct 2022 18:48 
Last Modified:  12 Oct 2022 18:49 
Primary Research Area:  NRA1: Trustworthy Information Processing 
URI:  https://publications.cispa.saarland/id/eprint/3804 
Actions
Actions (login required)
View Item 