- 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.