New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k-Disjoint Cycles on Plane and Planar Graphs

We present new fixed parameter algorithms for the face cover problem on plane graphs. We show that if a plane graph has a face cover with at most k faces then its treewidth is bounded by $$ O(\sqrt k )$$. An approximate tree decomposition can be obtained in linear time, and this is used to find an algorithm computing the face cover number in time $$ O(c^{\sqrt k } n)$$ for some constant c. Next we show that the problem is in linear time reducible to a problem kernel of O(k2) vertices, and this kernel can be used to obtain an algorithm that runs in time $$ O(c^{\sqrt k } + n)$$ for some other constant c. For the k-Disjoint Cycles problem and the kFEEDBACK VERTEX SET problem on planar graphs we obtain algorithms that run in time $$ O(c^{\sqrt k \log k} n)$$ for some constant c. For the k-FEEDBACK VERTEX SET problem we can further reduce the problem to a problem kernel of size O(k3) and obtain an algorithm that runs in time $$ O(c^{\sqrt k \log k} + n)$$ for some constant c1.