In Person Talk

For an oriented graph D and a set X of vertices of 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.

We answer several questions of Bang-Jensen, da Silva, and Havet:

(1)  We show that for each fixed k, it is possible to decide in quadratic time whether a tournament T has inversion number at most k. This exponent is optimal for all k.

(2) Building on their work, we prove their conjecture that for every k the problem is NP-complete for digraphs.

(3) We construct digraphs with inversion number equal to twice their cycle transversal number; and

(4) we disprove their conjecture concerning the inversion number of so-called `dijoin' digraphs.

Joint work with Emil Powierski, Michael Savery and Elizabeth Wilmer.