caa a22 4500 445804521 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s00453-010-9390-4 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9390-4 Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms [Elektronische Daten] [Athanassios Koutsonas, Dimitrios Thilikos] 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. Springer Science+Business Media, LLC, 2010 Branchwidth nationallicence Parameterized algorithms nationallicence Feedback vertex set nationallicence Face cover nationallicence Koutsonas Athanassios National and Kapodistrian University of Athens, Panepistimioupolis, 15784, Athens, Greece aut Thilikos Dimitrios National and Kapodistrian University of Athens, Panepistimioupolis, 15784, Athens, Greece aut Algorithmica Springer-Verlag 60/4(2011-08-01), 987-1003 0178-4617 60:4<987 2011 60 453 https://doi.org/10.1007/s00453-010-9390-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9390-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Koutsonas Athanassios National and Kapodistrian University of Athens, Panepistimioupolis, 15784, Athens, Greece aut NATIONALLICENCE 700 1- Thilikos Dimitrios National and Kapodistrian University of Athens, Panepistimioupolis, 15784, Athens, Greece aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/4(2011-08-01), 987-1003 0178-4617 60:4<987 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer