Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms |
| |
Authors: | Athanassios Koutsonas Dimitrios M Thilikos |
| |
Affiliation: | (1) 84081 Baronissi, Salerno, (SA), Italy;(2) Dip. Mat. e Inform., Univ. Salerno, 32611 Gainesville, FL, USA;(3) Center for Applied Optim. Dept. Industrial and Systems Engin., Univ. Florida, 32611 Gainesville, FL, USA;(4) Information Sci. Res. AT&T Labs Res., Florham Park, Florham Park, 07932, NJ, USA |
| |
Abstract: | The Planar Feedback Vertex Set problem asks whether an n-vertex planar graph contains at most k vertices meeting all its cycles. The Face Cover problem asks whether all vertices of a plane graph G lie on the boundary of at most k faces of G. Standard techniques from parameterized algorithm design indicate that both problems can be solved by sub-exponential parameterized algorithms (where k is the parameter). In this paper we improve the algorithmic analysis of both problems by proving a series of combinatorial results relating the branchwidth of planar graphs with their face cover. Combining this fact with duality properties of branchwidth, allows us to derive analogous results on feedback vertex set. As a consequence, it follows that Planar Feedback Vertex Set and Face Cover can be solved in \(O(2^{15.11\cdot\sqrt{k}}+n^{2})\) and \(O(2^{10.1\cdot\sqrt {k}}+n^{2})\) steps, respectively. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|