Fractional majority coloring of digraphs: bounds and inapproximability

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<3.736\), improving the bound \(3.9602\) of Anastos, Lamaison, Steiner and Szab\'o. Our construction uses exclusive sampling from pairs in random cycle matchings, followed by deletion and a correction on the acyclic remainder. The same approach yields bounds below \(3.430\) for digraphs with a directed cycle factor, \(3.287\) for those with an even cycle factor, and \(3.324\) for tournaments. As a consequence, for every fixed \(\varepsilon>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.