Fractional majority coloring of digraphs: bounds and inapproximability

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\mathrm{/}140<3.736$, improving the bound $3.9602$ of Anastos, Lamaison, Steiner and Szabó. 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 $\epsilon >0$, we obtain a randomized $(2.491+\epsilon )$-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\mathrm{/}2$, and establish a multiplicative inapproximability threshold of $72\mathrm{/}71$ and an additive upper-estimation threshold of $3\mathrm{/}142$. All three results hold for acyclic oriented digraphs with outdegrees zero or two in which every directed path has length at most two.