Abstract
In kDigraph Coloring we are given a digraph and are asked to partition its vertices into at most k sets, so that each set induces a DAG. This wellknown problem is NPhard, as it generalizes (undirected) kColoring, but becomes trivial if the input digraph is acyclic. This poses the natural parameterized complexity question of what happens when the input is "almost" acyclic. In this paper we study this question using parameters that measure the input’s distance to acyclicity in either the directed or the undirected sense.
In the directed sense perhaps the most natural notion of distance to acyclicity is directed feedback vertex set (DFVS). It is already known that, for all k ≥ 2, kDigraph Coloring is NPhard on digraphs of DFVS at most k+4. We strengthen this result to show that, for all k ≥ 2, kDigraph Coloring is already NPhard for DFVS exactly k. This immediately provides a dichotomy, as kDigraph Coloring is trivial if DFVS is at most k1. Refining our reduction we obtain two further consequences: (i) for all k ≥ 2, kDigraph Coloring is NPhard for graphs of feedback arc set (FAS) at most k²; interestingly, this leads to a second dichotomy, as we show that the problem is FPT by k if FAS is at most k²1; (ii) kDigraph Coloring is NPhard for graphs of DFVS k, even if the maximum degree Δ is at most 4k1; we show that this is also almost tight, as the problem becomes FPT for DFVS k and Δ ≤ 4k3.
Since these results imply that the problem is also NPhard on graphs of bounded directed treewidth, we then consider parameters that measure the distance from acyclicity of the underlying graph. On the positive side, we show that kDigraph Coloring admits an FPT algorithm parameterized by treewidth, whose parameter dependence is (tw!)k^{tw}. Since this is considerably worse than the k^{tw} dependence of (undirected) kColoring, we pose the question of whether the tw! factor can be eliminated. Our main contribution in this part is to settle this question in the negative and show that our algorithm is essentially optimal, even for the much more restricted parameter treedepth and for k = 2. Specifically, we show that an FPT algorithm solving 2Digraph Coloring with dependence td^o(td) would contradict the ETH.
BibTeX  Entry
@InProceedings{harutyunyan_et_al:LIPIcs.STACS.2021.41,
author = {Harutyunyan, Ararat and Lampis, Michael and Melissinos, Nikolaos},
title = {{Digraph Coloring and Distance to Acyclicity}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {41:141:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771801},
ISSN = {18688969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13686},
URN = {urn:nbn:de:0030drops136865},
doi = {10.4230/LIPIcs.STACS.2021.41},
annote = {Keywords: Digraph Coloring, Dichromatic number, NPcompleteness, Parameterized complexity, Feedback vertex and arc sets}
}
Keywords: 

Digraph Coloring, Dichromatic number, NPcompleteness, Parameterized complexity, Feedback vertex and arc sets 
Collection: 

38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) 
Issue Date: 

2021 
Date of publication: 

10.03.2021 