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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussavertaisarvioitu

Tutkijat

Organisaatiot

  • Max Planck Institute for Informatics

Kuvaus

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.

Yksityiskohdat

AlkuperäiskieliEnglanti
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

Julkaisusarja

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

Conference

ConferenceSymposium on Theoretical Aspects of Computer Science
LyhennettäSTACS
MaaSaksa
KaupunkiBerlin
Ajanjakso13/03/201916/03/2019

ID: 40353265