Jansen, Bart M. P. ;
Nederlof, Jesper
Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
Abstract
Computing the smallest number q such that the vertices of a given graph can be properly qcolored is one of the oldest and most fundamental problems in combinatorial optimization. The qColoring problem has been studied intensively using the framework of parameterized algorithmics, resulting in a very good understanding of the bestpossible 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^*(q^{tw}), while a running time of O^*((qepsilon)^{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 qColoring parameterized by cutwidth, and parameterized by pathwidth in boundeddegree graphs. Our research uncovers interesting new ways to exploit small edge separators.
We present two algorithms for qColoring parameterized by cutwidth {ctw}: a deterministic one that runs in time O^*(2^{omega * {ctw}}), where omega is the matrix multiplication constant, and a randomized one with runtime O^*(2^{{ctw}}). In sharp contrast to earlier work, the running time is independent of q. The dependence on cutwidth is optimal: we prove that even 3Coloring cannot be solved in O^*((2epsilon)^{{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^*((floor[d/2]+1)^{{pw}}) time randomized algorithm for qColoring 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^*((floor[d/2]+1epsilon)^{{pw}})time algorithm exists assuming SETH.
BibTeX  Entry
@InProceedings{jansen_et_al:LIPIcs:2018:9510,
author = {Bart M. P. Jansen and Jesper Nederlof},
title = {{Computing the Chromatic Number Using Graph Decompositions via Matrix Rank}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {47:147:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9510},
URN = {urn:nbn:de:0030drops95104},
doi = {10.4230/LIPIcs.ESA.2018.47},
annote = {Keywords: Parameterized Complexity, Chromatic Number, Graph Decompositions}
}
14.08.2018
Keywords: 

Parameterized Complexity, Chromatic Number, Graph Decompositions 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

14.08.2018 