Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization |
| |
Authors: | Jiong Guo,Jens Gramm,Falk Hü ffner,Rolf Niedermeier |
| |
Affiliation: | a Institut für Informatik, Friedrich-Schiller-Universität Jena, Ernst-Abbe-Platz 2, D-07743 Jena, Germany b Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany |
| |
Abstract: | We show that the NP-complete Feedback Vertex Set problem, which asks for the smallest set of vertices to remove from a graph to destroy all cycles, is deterministically solvable in O(ck⋅m) time. Here, m denotes the number of graph edges, k denotes the size of the feedback vertex set searched for, and c is a constant. We extend this to an algorithm enumerating all solutions in O(dk⋅m) time for a (larger) constant d. As a further result, we present a fixed-parameter algorithm with runtime O(k2⋅m2) for the NP-complete Edge Bipartization problem, which asks for at most k edges to remove from a graph to make it bipartite. |
| |
Keywords: | Fixed-parameter tractability Iterative compression Graph algorithm Graph modification problem Feedback set problem |
本文献已被 ScienceDirect 等数据库收录! |
|