Some polynomial classes for the acyclic orientation with parity constraint problem

Sylvain Gravier, Matthieu Petiteau, Isabelle Sivignon

We study the problem of finding an acyclic orientation of an undirected graph with constrained in-degree parities specified by a subset T of vertices. An orientation is called T -o…