Loading Events

« All Events

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


November 22, 2023
3:30 pm - 4:30 pm
Event Category:


Online via Zoom


jeannette Janssen
(902) 494-8851