English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

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

MPS-Authors
/persons/resource/persons98366

Schmid,  Andreas
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

arXiv:1804.03485.pdf
(Preprint), 3MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Chalermsook, P., Schmid, A., & Uniyal, S. (2018). A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs. Retrieved from http://arxiv.org/abs/1804.03485.


Cite as: http://hdl.handle.net/21.11116/0000-0002-E5D0-0
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 $\frac{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 $\frac{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 $\frac{1}{11}$-approximation; (ii) An alternate (and arguably more illustrative) proof of the $\frac{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.