Majority 2-coloring recognition complexity

Open Problem 5 · arXiv:1608.03040

arXiv Problem high confidence— first stated 2016-08-10

Authors: Stephan Kreutzer, Sang-il Oum, Paul Seymour, Dominic van der Zypen, David R. Wood

Status partial high confidence

The algorithmic half of Open Problem 5 is settled: Anastos, Lamaison, Steiner, and Szabó (arXiv:1911.01954) proved that deciding whether a given digraph is majority 2-colorable is NP-complete (Theorem 9), ruling out a polynomial-time recognition algorithm unless P=NP. The structural-characterisation half of the question remains open, as no combinatorial characterisation of majority 2-colorable digraphs is known.

Cited literature (1)

partial Majority Colorings of Sparse Digraphs (2019)

Michael Anastos, Ander Lamaison, Raphael Steiner, Tibor Szabó · arXiv preprint · arXiv:1911.01954

Proves that deciding whether a digraph is majority 2-colorable is NP-complete (Theorem 9), answering the polynomial-time algorithm part of Open Problem 5 negatively; the structural characterisation question remains open.

Reviewer notes. Open Problem 5 asks two things: (1) a characterisation of majority 2-colorable digraphs, or (2) a polynomial-time algorithm. The NP-completeness result in 1911.01954 definitively closes question (2). Question (1) remains open; a 2025 paper (Acta Math. Appl. Sinica) on majority coloring of digraphs was found but is behind a paywall and could not be verified. A 2024 arXiv paper (2406.04189) on countable DAGs addresses a different variant and does not resolve the finite characterisation question.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Is there a characterisation of digraphs that have a majority 2-colouring, or a polynomial-time algorithm to recognise such digraphs?

Context

Majority 2-colourability is not closed under taking induced subdigraphs (an example with four vertices is given in the introduction), making a simple hereditary characterisation impossible; no structural characterisation or efficient recognition algorithm is known.

Source paper

Majority Colourings of Digraphs
Stephan Kreutzer, Sang-il Oum, Paul Seymour, Dominic van der Zypen, David R. Wood · 2016-08-10
https://arxiv.org/abs/1608.03040 PDF source