Back to Search
Start Over
Parameterized (Approximate) Defective Coloring
- Source :
- SIAM Journal on Discrete Mathematics, SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2020, 34 (2), pp.1084-1106. ⟨10.1137/18M1223666⟩
- Publication Year :
- 2018
-
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 well-studied graph parameters, and show that the problem is W-hard parameterized by treewidth, pathwidth, tree-depth, 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 \ge 2$, and hence 2-coloring is the only hard case for this parameter. In addition to the above, we give an ETH-based 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 2-approximating 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/2$-approximation to $\chi_d$, even when an extra constant additive error is also allowed.<br />Comment: Accepted to STACS 2018
- Subjects :
- FOS: Computer and information sciences
Discrete mathematics
000 Computer science, knowledge, general works
General Mathematics
Parameterized complexity
0102 computer and information sciences
Computational Complexity (cs.CC)
01 natural sciences
Graph
Combinatorics
Treewidth
Computer Science - Computational Complexity
010201 computation theory & mathematics
Computer Science
Computer Science - Data Structures and Algorithms
Partition (number theory)
Data Structures and Algorithms (cs.DS)
[INFO]Computer Science [cs]
ComputingMilieux_MISCELLANEOUS
Mathematics
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Database :
- OpenAIRE
- Journal :
- SIAM Journal on Discrete Mathematics, SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2020, 34 (2), pp.1084-1106. ⟨10.1137/18M1223666⟩
- Accession number :
- edsair.doi.dedup.....20df10b7f0c266f968e631032a558538