Computing Square Colorings on Bounded-Treewidth and Planar Graphs

Akanksha Agrawal, Dániel Marx, Daniel Neuen, Jasper Slusallek

Submitted on 8 November 2022


A square coloring of a graph G is a coloring of the square G2 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 n2tw+4+O(1) for graphs of treewidth at most tw. The somewhat unusual exponent 2tw in the running time is essentially optimal: we show that for any ϵ>0, there is no algorithm with running time f(tw)n(2ϵ)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 q4 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 2O(n2/3logn) on planar graphs. The result follows from the combination of two algorithms. If the number q of colors is small (n1/3), then we can exploit a treewidth bound on the square of the graph to solve the problem in time 2O(qnlogn). If the number of colors is large (n1/3), then an algorithm based on protrusion decompositions and building on our result for the bounded-treewidth case solves the problem in time 2O(nlogn/q).


Comment: 72 pages, 15 figures, full version of a paper accepted at SODA 2023

Subjects: Computer Science - Data Structures and Algorithms; Computer Science - Discrete Mathematics