An acylic orientation problem with parity constraints

-- Matthieu Petiteau (Université Grenoble Alpes)

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.

Category: seminars
Tags: Team seminar graphs