Fomin, Fedor V. ;
Lokshtanov, Daniel ;
Panolan, Fahad ;
Saurabh, Saket ;
Zehavi, Meirav
Decomposition of Map Graphs with Applications
Abstract
Bidimensionality is the most common technique to design subexponentialtime parameterized algorithms on special classes of graphs, particularly planar graphs. The core engine behind it is a combinatorial lemma of Robertson, Seymour and Thomas that states that every planar graph either has a sqrt{k} x sqrt{k}grid as a minor, or its treewidth is O(sqrt{k}). However, bidimensionality theory cannot be extended directly to several wellknown classes of geometric graphs like unit disk or map graphs. This is mainly due to the presence of large cliques in these classes of graphs. Nevertheless, a relaxation of this lemma has been proven useful for unit disk graphs. Inspired by this, we prove a new decomposition lemma for map graphs, the intersection graphs of finitely many simplyconnected and interiordisjoint regions of the Euclidean plane. Informally, our lemma states the following. For any map graph G, there exists a collection (U_1,...,U_t) of cliques of G with the following property: G either contains a sqrt{k} x sqrt{k}grid as a minor, or it admits a tree decomposition where every bag is the union of O(sqrt{k}) cliques in the above collection.
The new lemma appears to be a handy tool in the design of subexponential parameterized algorithms on map graphs. We demonstrate its usability by designing algorithms on map graphs with running time 2^{O({sqrt{k}log{k}})} * n^{O(1)} for Connected Planar FDeletion (that encompasses problems such as Feedback Vertex Set and Vertex Cover). Obtaining subexponential algorithms for Longest Cycle/Path and Cycle Packing is more challenging. We have to construct tree decompositions with more powerful properties and to prove sublinear bounds on the number of ways an optimum solution could "cross" bags in these decompositions.
For Longest Cycle/Path, these are the first subexponentialtime parameterized algorithm on map graphs. For Feedback Vertex Set and Cycle Packing, we improve upon known 2^{O({k^{0.75}log{k}})} * n^{O(1)}time algorithms on map graphs.
BibTeX  Entry
@InProceedings{fomin_et_al:LIPIcs:2019:10636,
author = {Fedor V. Fomin and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh and Meirav Zehavi},
title = {{Decomposition of Map Graphs with Applications}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {60:160:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10636},
URN = {urn:nbn:de:0030drops106366},
doi = {10.4230/LIPIcs.ICALP.2019.60},
annote = {Keywords: Longest Cycle, Cycle Packing, Feedback Vertex Set, Map Graphs, FPT}
}
04.07.2019
Keywords: 

Longest Cycle, Cycle Packing, Feedback Vertex Set, Map Graphs, FPT 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 