License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.7
URN: urn:nbn:de:0030-drops-84815
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8481/
Agrawal, Akanksha ;
Lokshtanov, Daniel ;
Misra, Pranabendu ;
Saurabh, Saket ;
Zehavi, Meirav
Erdös-Pósa Property of Obstructions to Interval Graphs
Abstract
The duality between packing and covering problems lies at the heart of fundamental combinatorial proofs, as well as well-known algorithmic methods such as the primal-dual method for approximation and win/win-approach for parameterized analysis. The very essence of this duality is encompassed by a well-known property called the Erdös-Pósa property, which has been extensively studied for over five decades. Informally, we say that a class of graphs F admits the Erdös-Pósa property if there exists f such that for any graph G, either G has vertex-disjoint "copies" of the graphs in F, or there is a set S \subseteq V(G) of f(k) vertices that intersects all copies of the graphs in F. In the context of any graph class G, the most natural question that arises in this regard is as follows - do obstructions to G have the Erdös-Pósa property? Having this view in mind, we focus on the class of interval graphs. Structural properties of interval graphs are intensively studied, also as they lead to the design of polynomial-time algorithms for classic problems that are NP-hard on general graphs. Nevertheless, about one of the most basic properties of such graphs, namely, the Erdös-Pósa property, nothing is known. In this paper, we settle this anomaly: we prove that the family of obstructions to interval graphs - namely, the family of chordless cycles and ATs---admits the Erdös-Pósa property. Our main theorem immediately results in an algorithm to decide whether an input graph G has vertex-disjoint ATs and chordless cycles, or there exists a set of O(k^2 log k) vertices in G that hits all ATs and chordless cycles.
BibTeX - Entry
@InProceedings{agrawal_et_al:LIPIcs:2018:8481,
author = {Akanksha Agrawal and Daniel Lokshtanov and Pranabendu Misra and Saket Saurabh and Meirav Zehavi},
title = {{Erd{\"o}s-P{\'o}sa Property of Obstructions to Interval Graphs}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {7:1--7:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-062-0},
ISSN = {1868-8969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8481},
URN = {urn:nbn:de:0030-drops-84815},
doi = {10.4230/LIPIcs.STACS.2018.7},
annote = {Keywords: Interval Graphs, Obstructions, Erd{\"o}s-P{\'o}sa Property}
}
|
Keywords: |
|
Interval Graphs, Obstructions, Erdös-Pósa Property |
|
Collection: |
|
35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
27.02.2018 |
