A MIN-MAX THEOREM ON TOURNAMENTS.

We present a structural characterization of all tournaments T = (V,A) such that, for any nonnegative integral weight function defined on V , the maximum size of a feedback vertex set packing is equal to the minimum weight of a triangle in T. We also answer a question of Frank by showing that it is NP-complete to decide whether the vertex set of a given tournament can be partitioned into two feedback vertex sets. In addition, we give exact and approximation algorithms for the feedback vertex set packing problem on tournaments. [ABSTRACT FROM AUTHOR]