论文摘要：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 partitionedinto two feedback vertex sets. In addition, we give exact and approximation algorithms for the feedback vertex set packing problem on tournaments.
论文题目: A Min-Max theorem on tournaments
论文作者: 陈旭瑾和胡晓东（应用数学所）, 藏文安（香港大学数学系）
发表刊物: SIAM Journal on Computing，37(3)(2007), 923-937
附件下载：
