Note about the complexity of the acyclic orientation with parity constraint problem
Sylvain Gravier, Matthieu Petiteau, Isabelle Sivignon · 2025
Read Note about the complexity of the acyclic orientation with parity constraint problem by Sylvain Gravier, Matthieu Petiteau, Isabelle Sivignon (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-20935.txt.
Description
Sylvain Gravier, Matthieu Petiteau, and Isabelle Sivignon settle a hardness result for graph orientations in this 2025 paper. An orientation points each edge of a graph one way. A T-odd orientation demands odd in-degree exactly at a chosen vertex set.
Plain T-odd orientation can be found fast, a fact known since 1983. Adding a ban on directed cycles makes the problem far thornier. A randomized method exists, and flat graphs have a full solution in one case. The authors study a wider version where some edges come pre-pointed. They prove that version is NP-complete. The result tightens what is known about this long-open problem.
Catalog record
| CREATOR | Sylvain Gravier, Matthieu Petiteau, Isabelle Sivignon |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-20935