A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
Date
2019
Major/Subject
Mcode
Degree programme
Language
en
Pages
14
1-14
Series
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), Leibniz international proceedings in informatics, Volume 126
Abstract
A cactus graph is a graph in which any two cycles are edge-disjoint. We present a constructive proof of the fact that any plane graph G contains a cactus subgraph C where C contains at least a 1/6 fraction of the triangular faces of G. We also show that this ratio cannot be improved by showing a tight lower bound. Together with an algorithm for linear matroid parity, our bound implies two approximation algorithms for computing "dense planar structures" inside any graph: (i) A 1/6 approximation algorithm for, given any graph G, finding a planar subgraph with a maximum number of triangular faces; this improves upon the previous 1/11-approximation; (ii) An alternate (and arguably more illustrative) proof of the 4/9 approximation algorithm for finding a planar subgraph with a maximum number of edges. Our bound is obtained by analyzing a natural local search strategy and heavily exploiting the exchange arguments. Therefore, this suggests the power of local search in handling problems of this kind.
Description
Keywords
Other note
Citation
Chalermsook , P , Schmid , A & Uniyal , S 2019 , A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs . in 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) . , 19 , Leibniz international proceedings in informatics , vol. 126 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik , pp. 1-14 , Symposium on Theoretical Aspects of Computer Science , Berlin , Germany , 13/03/2019 . https://doi.org/10.4230/LIPIcs.STACS.2019.19