document: A min-max theorem on feedback vertex sets We establish a necessary and sufficient condition for the linear system -LCB- x : Hx > or = e , x > or = 0 -RCB- associated with a bipartite tournament to be totally dual integral , 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 min-max theorem
doc_bio_tags: O O O O B I I O O O O O O O O O B I O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O B I I I O O B I I I O O B I I O O O O O O O O O O O O O B I I I O O O O O O O O O O O O O O O
extractive_keyphrases: feedback vertex sets linear system bipartite tournament covering cycles strongly polynomial time algorithms cycle packing problem feedback vertex set problem
abstractive_keyphrases: min-max theorem necessary sufficient condition totally dual integral system cycle-vertex incidence matrix all-one vector np-complete problem graphs combinatorial optimization problems linear programming duality theory