Belmonte, Rémy ;
Lampis, Michael ;
Mitsou, Valia
Parameterized (Approximate) Defective Coloring
Abstract
In Defective Coloring we are given a graph G=(V,E) and two integers chi_d,Delta^* and are asked if we can partition V into chi_d color classes, so that each class induces a graph of maximum degree Delta^*. We investigate the complexity of this generalization of Coloring with respect to several wellstudied graph parameters, and show that the problem is Whard parameterized by treewidth, pathwidth, treedepth, or feedback vertex set, if chi_d=2. As expected, this hardness can be extended to larger values of chi_d for most of these parameters, with one surprising exception: we show that the problem is FPT parameterized by feedback vertex set for any chi_d != 2, and hence 2coloring is the only hard case for this parameter. In addition to the above, we give an ETHbased lower bound for treewidth and pathwidth, showing that no algorithm can solve the
problem in n^{o(pw)}, essentially matching the complexity of an algorithm obtained with standard techniques.
We complement these results by considering the problem's approximability and show that, with respect to Delta^*, the problem admits an algorithm which for any epsilon>0 runs in time (tw/epsilon)^{O(tw)} and returns a solution with exactly the desired number of colors that approximates the optimal Delta^* within (1+epsilon). We also give a (tw)^{O(tw)} algorithm which achieves the desired Delta^* exactly while 2approximating the minimum value of chi_d. We show that this is close to optimal, by establishing that no FPT algorithm can (under standard assumptions) achieve a better than 3/2approximation to chi_d, even when an extra constant additive error is also allowed.
BibTeX  Entry
@InProceedings{belmonte_et_al:LIPIcs:2018:8530,
author = {R{\'e}my Belmonte and Michael Lampis and Valia Mitsou},
title = {{Parameterized (Approximate) Defective Coloring}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {10:110:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770620},
ISSN = {18688969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8530},
URN = {urn:nbn:de:0030drops85304},
doi = {10.4230/LIPIcs.STACS.2018.10},
annote = {Keywords: Treewidth, Parameterized Complexity, Approximation, Coloring}
}
27.02.2018
Keywords: 

Treewidth, Parameterized Complexity, Approximation, Coloring 
Seminar: 

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Issue date: 

2018 
Date of publication: 

27.02.2018 