2006 | OriginalPaper | Chapter
Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
Authors : Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, Anke Truß
Published in: Algorithms and Complexity
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Complementing recent progress on classical complexity and polynomial-time approximability of feedback set problems in (bipartite) tournaments, we extend and partially improve fixed-parameter tractability results for these problems. We show that
Feedback Vertex Set
in tournaments is amenable to the novel iterative compression technique. Moreover, we provide data reductions and problem kernels for
Feedback Vertex Set
and
Feedback Arc Set
in tournaments, and a depth-bounded search tree for
Feedback Arc Set
in bipartite tournaments based on a new forbidden subgraph characterization.