- This event has passed.
Atlantic Graph Theory Seminar
November 22, 2023 @ 3:30 pm - 4:30 pm
Speaker: Santiago Guzman-Pro, TU Dresden
Title: Forbidden Tournaments and the Orientation (Completion) Problem
Abstract: For a fixed finite set of oriented graphs F, the F-free orientation problem asks
whether a given finite undirected graph G has an F-free orientation, i.e., whether the edges
of G can be oriented so that the resulting oriented graph does not contain any oriented
graph from F as an oriented (induced) subgraph. It was first noted by Bang-Jensen, Huang,
and Prisner that when F is a set of oriented paths on 3 vertices, this problem easily reduces
to 2-SAT, and thus is solvable in polynomial-time. This was later extended to sets of oriented
graphs on 3 vertices (G.P.\ and Hernández-Cruz 2017). Towards a complete understanding
of the complexity of the F-free orientation problem, we consider the case when F is a set of
finite tournaments. We prove that for every such F, this problem is in P or NP-complete.Specifically, we show that either the F-free orientation problem can be reduced (in polynomial-
time) to a system of Boolean linear equations, or the F-free orientation problem is NP-complete.
This dichotomy result is accompanied by a classification statement which, given a set of
tournaments F, allows us to decide whether the F-free orientation problem is in P or
NP-complete. We reduce this classification task to a complete complexity classification of the
orientation completion problem for F, which is the variant of the problem above where the input
is a partially oriented graph instead of an undirected graph, introduced by Bang-Jensen, Huang,
and Zhu (2017). Our proof uses results from the theory of constraint satisfaction, and a result
of Agarwal and Kompatscher (2018) about infinite permutation groups and transformation monoids.
This is joint work with Manuel Bodirsky.