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/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,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.11997
curl -X POST /api/v1/records/arxiv/2610.11997/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.11997/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'