Algebra Seminar talk
2024-06-14
Roman Feller
The graph orientation problem for forbidden tournaments
Abstract:
For a set of oriented graphs F, the F-free orientation problem is defined as follows: Given a finite undirected graph G, is there an orientation of the edges of G such that the resulting directed graph does not embed any member of F? If the set F consists of tournaments (i.e. complete oriented graphs) it was recently shown by Bodirsky and Guzmán-Pro that, depending on F, this computational problem is either solvable in polynomial time or NP-complete.
In this talk, I will explain how the F-free orientation problem can be viewed as the Constraint Satisfaction Problem (CSP) of an omega-categorical structure, making it amenable to universal algebraic methods. In particular I will demonstrate how the algebraic technique of smooth approximations, developed by Mottet and Pinsker, provides a shorter, algebraic proof of the complexity dichotomy for the F-free orientation problem.
This is joint work with Michael Pinsker.