Michael Savery

Invertibility of digraphs and tournaments

For an oriented graph D and a set X\subset V(D), the inversion of X in D is the digraph obtained from D by reversing the orientations of all edges with both endpoints in X. The inversion number of D is the minimum number of inversions required to turn D into an acyclic digraph.

In this talk we will discuss the resolution of several recent conjectures and questions of Bang-Jensen, da Silva, and Havet. A particular focus will be the computational complexity of deciding for fixed k whether an input digraph D has inversion number at most k. We will see that in general this problem is NP-complete, but that when the input is restricted to tournaments it can be solved in quadratic time. We also study the natural extremal question in this setting, improving on previous bounds of Belkhechine, Bouaziz, Boudabbous, and Pouzet to show that the maximum inversion number of an n-vertex tournament is (1+o(1))n.

This is joint work with Noga Alon, Emil Powierski, Alex Scott, and Elizabeth Wilmer.