A Min-Max Theorem on Feedback Vertex Sets (Preliminary Version).

We establish a necessary and sufficient condition for the linear system {x : Hx ≥ e, x ≥ 0} associated with a bipartite tournament to be TDI, where H is the cycle-vertex incidence matrix and e is the all-one vector. The consequence is a min-max relation on packing and covering cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem on the corresponding bipartite tournaments. In addition, we show that the feedback vertex set problem on general bipartite tournaments is NP-complete and approximable within 3.5 based on the max-min theorem. [ABSTRACT FROM AUTHOR]