A min–max theorem on feedback vertex sets

A min–max theorem on feedback vertex sets

0.00 Avg rating0 Votes
Article ID: iaor2004421
Country: United States
Volume: 27
Issue: 2
Start Page Number: 361
End Page Number: 371
Publication Date: May 2002
Journal: Mathematics of Operations Research
Authors: , ,
Abstract:

We establish a necessary and sufficient condition for the linear system {x ; Hx ≥ e, x ≥ 0} 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.

Reviews

Required fields are marked *. Your email address will not be published.