کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430633 | 688072 | 2010 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Fixed-parameter tractability results for feedback set problems in tournaments Fixed-parameter tractability results for feedback set problems in tournaments](/preview/png/430633.png)
Complementing recent progress on classical complexity and polynomial-time approximability of feedback set problems in (bipartite) tournaments, we extend and improve fixed-parameter tractability results for these problems. We show that Feedback Vertex Set in tournaments (FVST) is amenable to the novel iterative compression technique, and we provide a depth-bounded search tree for Feedback Arc Set in bipartite tournaments based on a new forbidden subgraph characterization. Moreover, we apply the iterative compression technique to d-Hitting Set, which generalizes Feedback Vertex Set in tournaments, and obtain improved upper bounds for the time needed to solve 4-Hitting Set and 5-Hitting Set. Using our parameterized algorithm for Feedback Vertex Set in tournaments, we also give an exact (not parameterized) algorithm for it running in O(n1.709)O(1.709n) time, where n is the number of input graph vertices, answering a question of Woeginger [G.J. Woeginger, Open problems around exact algorithms, Discrete Appl. Math. 156 (3) (2008) 397–405].
Journal: Journal of Discrete Algorithms - Volume 8, Issue 1, March 2010, Pages 76–86