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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussavertaisarvioitu



  • Max Planck Institute for Informatics


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.


Otsikko36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
TilaJulkaistu - 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaSymposium on Theoretical Aspects of Computer Science - Berlin, Saksa
Kesto: 13 maaliskuuta 201916 maaliskuuta 2019
Konferenssinumero: 36


NimiLeibniz international proceedings in informatics
KustantajaSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISSN (elektroninen)1868-8969


ConferenceSymposium on Theoretical Aspects of Computer Science

ID: 40353265