Fractional majority coloring of digraphs: bounds and inapproximability

Source abstract

A set of vertices in a digraph is majority-stable if each of its vertices has at most half of its outneighbors in the set. A fractional majority coloring assigns nonnegative weights to such sets, covering each vertex to total weight at least one; its minimum total weight is the fractional majority coloring number. We prove that every finite loopless digraph has fractional majority coloring number at most $523/140 0$, we obtain a randomized $(2.491+\varepsilon)$-approximation algorithm producing an explicit fractional majority coloring in expected polynomial time. On the complexity side, we prove NP-completeness of deciding whether the fractional majority coloring number equals $3/2$, and establish a multiplicative inapproximability threshold of $72/71$ and an additive upper-estimation threshold of $3/142$. All three results hold for acyclic oriented digraphs with outdegrees zero or two in which every directed path has length at most two.