Pushing the cycles out of multipartite tournaments Original Research Article

Let D be a digraph and X⊆V(D). By pushingX we mean reversing each arc of D with exactly one end in X. Klostermeyer proved that it is NP-complete to decide if a given digraph can be made acyclic using the push operation. Here we characterize, in terms of forbidden subdigraphs, the multipartite tournaments which can be made acyclic (resp. ordinary, unidirectional) using the push operation. This implies that the problem of deciding if a given multipartite tournament can be made acyclic (resp. ordinary, unidirectional) using the push operation and, if so, finding a suitable subset of vertices to push, is solvable in polynomial time.