ON DISJOINT CYCLES
Hans L. Bodlaender · International Journal of Foundations of Computer Science · 1994
It is shown, that for each constant k≥1, the following problems can be solved in [Formula: see text] time: given a graph G, determine whether G has k vertex disjoint cycles, determine whether G has k edge disjoint cycles, determine whether G has a feedback vertex set of size ≤k. Also, every class [Formula: see text], that is closed under minor taking, taking, and that does not contain the graph consisting of k disjoint copies of K3, has an [Formula: see text] membership test algorithm.