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

CREATORSylvain Gravier, Matthieu Petiteau, Isabelle Sivignon
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-20935

Browse the full library · About the Tower of Babel