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ó. 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 ε>0, we obtain a randomized (2.491+ε)-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.
Related
- Randomized Borel (2d+1)-coloring of digraphs
- Majority C-coloring in Cartesian products
- Structural and computational aspects of majority coloring games
- On the disintegration of the stochastic majority vote: from pac-bayesian bounds to a self-bounding algorithm
- Bounds for B-coloring planar and outerplanar graphs
BibTeX
@misc{benameur2026fractional,
title = {{Fractional majority coloring of digraphs: bounds and inapproximability}},
author = {Walid Ben-Ameur and Alessandro Maddaloni},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11997},
eprint = {2610.11997},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11997},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Fractional majority coloring of digraphs: bounds and inapproximability
AU - Walid Ben-Ameur
AU - Alessandro Maddaloni
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.11997
UR - https://arxiv.org/abs/2610.11997
AB - 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ó. 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 ε>0, we obtain a randomized (2.491+ε)-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.
ER -