Settling a ten years open question, we show that the NP-complete FEEDBACK VERTEX SET problem is deterministically solvable in O(c~k · m) time, where m denotes the number of graph edges, k denotes the size of the feedback vertex set searched for, and c is a constant. As a second result, we present a fixed-parameter algorithm for the NP-complete EDGE BIPARTIZATION problem with runtime O(2~k · m~2).
展开▼
