<div class="csl-bib-body">
<div class="csl-entry">Feller, R. M. (2024, October 15). <i>Graph orientation problems with forbidden tournaments</i> [Presentation]. Panglobal Algebra and Logic Seminar 2024, Boulder, United States of America (the). https://doi.org/10.34726/8500</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/210542
-
dc.identifier.uri
https://doi.org/10.34726/8500
-
dc.description.abstract
Given a finite set of oriented graphs F, the F-free orientation problem is the following decision problem. Given a finite input graph, is there an orientation of its edges such that the resulting directed graph omits every member of F. If the set F consists of tournaments (i.e. complete oriented graphs), Bodirsky and Guzmán-Pro have recently established that this computational problem exhibits a complexity dichotomy: it is either solvable in polynomial time or NP-complete.
I will explain how the F-free orientation problem can be viewed as the constraint satisfaction problem (CSP) of an omega-categorical template, making it amenable to universal algebraic methods. In particular I will demonstrate how the recently developed technique of "smooth approximations", provides a shorter algebraic proof of the complexity dichotomy for the graph orientation problem.
