Abstract
Computing the smallest number q such that the vertices of a given graph can be
properly q-colored, known as the chromatic number, is one of the oldest and most
fundamental problems in combinatorial optimization. The q-Coloring problem has been
studied intensively using the framework of parameterized algorithmics, resulting in a very
good understanding of the best-possible algorithms for several parameterizations based
on the structure of the graph. For example, algorithms are known to solve the problem
on graphs of treewidth tw in time O∗(qtw), while a running time of O∗((q − ε)tw) is
impossible assuming the Strong Exponential Time Hypothesis (SETH). While there is an
abundance of work for parameterizations based on decompositions of the graph by vertex
separators, almost nothing is known about parameterizations based on edge separators.
We fill this gap by studying q-Coloring parameterized by cutwidth, and parameterized
by pathwidth in bounded-degree graphs. Our research uncovers interesting new ways to
exploit small edge separators.
We present two algorithms for q-Coloring parameterized by cutwidth ctw: a deterministic
one that runs in time O∗(2ω·ctw), where ω is the square matrix multiplication exponent,
and a randomized one with runtime O∗(2ctw). In sharp contrast to earlier work, the
running time is independent of q. The dependence on cutwidth is optimal: we prove that
even 3-Coloring cannot be solved in O∗((2 − ε)ctw) time assuming SETH. Our algorithms
rely on a new rank bound for a matrix that describes compatible colorings. Combined
with a simple communication protocol for evaluating a product of two polynomials, this
also yields an O∗((d/2 + 1)pw) time randomized algorithm for q-Coloring on graphs of
pathwidth pw and maximum degree d. Such a runtime was first obtained by Björklund,
but only for graphs with few proper colorings. We also prove that this result is optimal in
the sense that no O∗((d/2 + 1 − ε)pw)-time algorithm exists assuming SETH.
properly q-colored, known as the chromatic number, is one of the oldest and most
fundamental problems in combinatorial optimization. The q-Coloring problem has been
studied intensively using the framework of parameterized algorithmics, resulting in a very
good understanding of the best-possible algorithms for several parameterizations based
on the structure of the graph. For example, algorithms are known to solve the problem
on graphs of treewidth tw in time O∗(qtw), while a running time of O∗((q − ε)tw) is
impossible assuming the Strong Exponential Time Hypothesis (SETH). While there is an
abundance of work for parameterizations based on decompositions of the graph by vertex
separators, almost nothing is known about parameterizations based on edge separators.
We fill this gap by studying q-Coloring parameterized by cutwidth, and parameterized
by pathwidth in bounded-degree graphs. Our research uncovers interesting new ways to
exploit small edge separators.
We present two algorithms for q-Coloring parameterized by cutwidth ctw: a deterministic
one that runs in time O∗(2ω·ctw), where ω is the square matrix multiplication exponent,
and a randomized one with runtime O∗(2ctw). In sharp contrast to earlier work, the
running time is independent of q. The dependence on cutwidth is optimal: we prove that
even 3-Coloring cannot be solved in O∗((2 − ε)ctw) time assuming SETH. Our algorithms
rely on a new rank bound for a matrix that describes compatible colorings. Combined
with a simple communication protocol for evaluating a product of two polynomials, this
also yields an O∗((d/2 + 1)pw) time randomized algorithm for q-Coloring on graphs of
pathwidth pw and maximum degree d. Such a runtime was first obtained by Björklund,
but only for graphs with few proper colorings. We also prove that this result is optimal in
the sense that no O∗((d/2 + 1 − ε)pw)-time algorithm exists assuming SETH.
| Original language | English |
|---|---|
| Pages (from-to) | 520-539 |
| Journal | Theoretical Computer Science |
| Volume | 795 |
| DOIs | |
| Publication status | Published - 2019 |
| Externally published | Yes |