Hardness and Approximation for Coloring Digraphs
For researchers in graph theory and approximation algorithms, this paper provides hardness results and new algorithmic bounds for coloring digraphs, though the results are incremental in nature.
The paper studies approximation algorithms for the dichromatic number and acyclic number of digraphs. It shows that even for tournaments, these problems are as hard to approximate as their undirected counterparts, and provides algorithms for special cases such as 2-dicolorable digraphs and dense digraphs without directed triangles.
The dichromatic number $\vecχ(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 $\vecα(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 $\vecχ$ and $\vecα$ remain as challenging as their undirected counterparts on general graphs. Specifically, we establish that for every $ε>0$, it is hard to approximate both $\vecα$ and $\vecχ$ 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 $\ell$-dicolorable digraphs using at most $\ell \cdot n^{1-\frac{1}{\ell}}$ colors in time $O(n^{2\ell})$; in particular, we can color $2$-dicolorable digraphs with $2\sqrt{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 $\vecχ(D)\leq 2$ and digraphs that do not contain any directed triangle. For these cases, we present algorithms which generalize and improve existing tools and results.