An acylic orientation problem with parity constraints
Time: 14:00 -- Location: LRI, 445
summary: Let G = (V, E) be a connected graph and T be a subset of the vertices.
An orientation of G is a choice of a direction for each edge of the graph, it
is said to be acylic if does not contain any directed cycle. An orientation of G
is said T-odd if a vertex have odd indegree if and only if it is in T. Finding a
T-odd orientation of G can be solved in polynomial time as Chevalier et al.
proved in 1983. From then, T-odd continued to wield interest considering constraint
on the orientation. Indeed, Frank et Király 2002 looked at k-connected T-odd orientations
and raise questions about acyclic T-odd orientations. This problem is now registered
as an Egres problem and is known as the "Acyclic orientation with parity constraints" problem.
It is still unknown whether it is NP-complete or not, even though, Szegedy suggest it is polynomial.
In this talk we will go through the basic results on this problem and discuss about its complexity.