New algorithms for \(k\)-face cover, \(k\)-feedback vertex set, and \(k\)-disjoint cycles on plane and planar graphs. (English) Zbl 1022.68100

Kloks, Ton; Lee, C. M.; Liu, Jiping

Kučera, Luděk (ed.), Graph-theoretic concepts in computer science. 28th international workshop, WG 2002, Český Krumlov, Czech Republic, June 13-15, 2002. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 2573, 282-295 (2002).

Summary: 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(k^{2})\) 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 \(k\)-FEEDBACK 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 VERTEXS ET problem we can further reduce the problem to a problem kernel of size \(O(k^{3})\) and obtain an algorithm that runs in time \(O(c^{\sqrt{k}\log{k}}+n)\) for some constant \(c\).
For the entire collection see [Zbl 1013.00032].

MSC:

68R10	Graph theory (including graph drawing) in computer science
05C85	Graph algorithms (graph-theoretic aspects)
68Q25	Analysis of algorithms and problem complexity