2026-09-05T11:38:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26442 2026-08-27T14:39:34Z ddc:004 open_access

Hardness and Approximation for Coloring Digraphs Chalermsook, Parinya Gahlawat, Harmender Klingelhoefer, Felix Newman, Alantha Tang, Chaoliang Graph Algorithms Hardness of Approximation Polynomial Time Approximation Algorithms Structural Graph Theory The dichromatic number χ(D) of a digraph is the minimum number k such that V(D) can be partitioned into k subsets, each inducing an acyclic digraph. The acyclic number α(D) is the cardinality of a largest induced acyclic subdigraph of D. We study these problems from an approximation point of view. We begin with establishing that even when restricted to tournaments, approximating χ and α remain as challenging as their undirected counterparts on general graphs. Specifically, we establish that for every ε > 0, it is hard to approximate both α and χ up to a factor of n^{1-ε} even when restricted to tournaments. We next consider approximate coloring of digraphs in special cases. We begin with establishing that we can color 𝓁-dicolorable digraphs using at most 𝓁 ⋅ n^{1-1/(𝓁)} colors in time O(n^{2𝓁}); in particular, we can color 2-dicolorable digraphs with 2√n colors in polynomial time. We then focus on bounding the dichromatic number of dense digraphs as a function of the independence number α of the underlying graph. We consider two special cases in this regard: digraphs with χ(D) ≤ 2 and digraphs that do not contain any directed triangle. For these cases, we present algorithms which generalize and improve existing tools and results. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Parinya Chalermsook and Harmender Gahlawat and Felix Klingelhoefer and Alantha Newman and Chaoliang Tang 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.53 urn:nbn:de:0030-drops-264421 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.53 eng https://creativecommons.org/licenses/by/4.0/legalcode