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

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Researchers

Research units

  • Max Planck Institute for Informatics

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.

Details

Original languageEnglish
Title of host publication36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Publication statusPublished - 2019
MoE publication typeA4 Article in a conference publication
EventSymposium on Theoretical Aspects of Computer Science - Berlin, Germany
Duration: 13 Mar 201916 Mar 2019
Conference number: 36

Publication series

NameLeibniz international proceedings in informatics
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume126
ISSN (Electronic)1868-8969

Conference

ConferenceSymposium on Theoretical Aspects of Computer Science
Abbreviated titleSTACS
CountryGermany
CityBerlin
Period13/03/201916/03/2019

ID: 40353265