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.
Graph orientation problems with forbidden tournaments
Tue, Oct. 15 3:30pm (MATH 3…
Topology
Courtney Hauf
X
After decades of development, we reached a construction of algebraic K-theory that checked all the boxes: Waldhausen’s S-construction. Extending this construction to oo-categories, we can (nicely) discuss the algebraic K-theory of (ring) spectra, spaces, and more. In this talk we will see the S-construction applied to oo-categories and discuss some of the ways we can utilize algebraic K-theory of oo-categories.
[Will volley off the ideas Sylvia presented for oo-categories.]
Graph orientation problems with forbidden tournaments