A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
14
Series
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), pp. 1-14, 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