cispa_all_3804.pdf (916.82 kB)

# Computing Square Colorings on Bounded-Treewidth and Planar Graphs

conference contribution

posted on 2023-11-29, 18:25 authored by Akanksha Agrawal, Dániel MarxDániel Marx, Daniel Neuen, Jasper SlusallekA {\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 polynomial-time 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 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)}$.

## History

## Preferred Citation

Akanksha Agrawal, Dániel Marx, Daniel Neuen and Jasper Slusallek. Computing Square Colorings on Bounded-Treewidth and Planar Graphs. In: ACM-SIAM Symposium on Discrete Algorithms (SODA). 2023.## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

ACM-SIAM Symposium on Discrete Algorithms (SODA)## Legacy Posted Date

2022-10-12## Open Access Type

- Green

## BibTeX

@inproceedings{cispa_all_3804, title = "Computing Square Colorings on Bounded-Treewidth and Planar Graphs", author = "Agrawal, Akanksha and Marx, Dániel and Neuen, Daniel and Slusallek, Jasper", booktitle="{ACM-SIAM Symposium on Discrete Algorithms (SODA)}", year="2023", }## Usage metrics

## Categories

No categories selected## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC