Powers of Directed Hamiltonian Paths as Feedback Arc Sets

Abstract

Given an acyclic digraph $D$, we seek a smallest sized tournament $T$ having $D$ as a minimum feedback arc set. The reversing number of a digraph is defined to be

$$r(D)=|V(T)|–|V(D)|.$$

We use integer programming methods to obtain new results for the reversing number where $D$ is a power of a directed Hamiltonian path. As a result, we establish that known reversing numbers for certain classes of tournaments actually suffice for a larger class of digraphs.