zbMATH — the first resource for mathematics

Fixed-parameter tractability results for feedback set problems in tournaments. (English) Zbl 1183.68419
Calamoneri, Tiziana (ed.) et al., Algorithms and complexity. 6th Italian conference, CIAC 2006, Rome, Italy, May 29–31, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34375-X/pbk). Lecture Notes in Computer Science 3998, 320-331 (2006).
Summary: 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.
For the entire collection see [Zbl 1103.68003].

68R10 Graph theory (including graph drawing) in computer science
05C20 Directed graphs (digraphs), tournaments
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI