Subexponential Parameterized Algorithms on Disk Graphs (Extended Abstract)

Lokshtanov, D. and Panolan, F. and Saurab, S. and et al, . (2022) Subexponential Parameterized Algorithms on Disk Graphs (Extended Abstract). In: 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, 9 January 2022 through 12 January 2022, Alexander.

Text
Proceedings_of_the_Annual_ACM_SIAM_Symposium_on_Discrete_Algorithms.pdf - Published Version
Restricted to Registered users only
Download (1MB) | Request a copy

Abstract

One of the most celebrated results in Parameterized Complexity is the Bidimensionality theory of Demaine et al. J. ACM, 2005, which has yielded, over the past two decades, numerous subexponential-time fixedparameter tractable (FPT) algorithms for various problems on planar (and H-minor-free) graphs. At the heart of this theory is the proof of sublinear bounds in terms of solution size on the treewidth of a given graph. Inspired by this theory, in recent years, significant efiorts have been devoted to design subexponential-time FPT algorithms for problems on geometric graph classes that utilize new treewidth bounds, in particular (but not only) for unit disk graphs Fomin et al., SODA'12; Fomin et al., DCG'19; Panolan et al., SODA'19; Fomin et al. SoCG'20. In this paper, we aim to attain such results on disk graphs, a broad class of graphs that generalizes both the classes of planar graphs and unit disk graphs, and thereby unify the aforementioned research frontiers for planar and unit disk graphs. Our main contribution is an approach to design subexponential-time FPT algorithms for problems on disk graphs, which we apply to several well-studied graph problems. At the heart of our approach lie two new combinatorial theorems concerning the treewidth of disk graphs having a realization of bounded ply (or maximum clique size) that are of independent interest. In particular, we prove a stronger version of the following treewidth bound: Let G be a disk graph that has some realization of ply p and no false twins, and M V (G) such that G has no triangle with exactly one vertex from M, and G M has treewidth w. Then, the treewidth of G is O(maxf p jMj w p2:5;w pg). Among our applications are the first subexponential-time FPT algorithms for several problems on disk graphs, including Triangle Hitting, Feedback Vertex Set and Odd Cycle Transversal (OCT). Previously, subexponential-time FPT algorithms for these problems were only known on planar graphs and unit disk graphs (excluding OCT, which was only known to admit such an algorithm on planar graphs). Our algorithms are robust, in particular, they do not require a geometric realization of the input graph (for all aforementioned problems), and they generalize to the weighted and counting versions of all aforementioned problems except for OCT. Copyright Â© 2022 by SIAM.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Panolan, Fahad	https://orcid.org/0000-0001-6213-8687

Item Type:

Conference or Workshop Item (Paper)

Additional Information:

∗S. Saurabh is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 819416), and Swarnajayanti Fellowship (No DST/SJF/MSA01/2017-18). D. Lokshtanov and M. Zehavi are supported by United States – Israel Binational Science Foundation (BSF) grant no. 2018302. D. Lokshtanov is supported by National Science Foundation (NSF) award CCF-2008838. M. Zehavi is supported by Israel Science Foundation (ISF) grant no. 1176/18. †University of California, Santa Barbara, US. daniello@ucsb.edu ‡Department of Computer Science and Engineering, IIT Hyderabad, India. fahad@cse.iith.ac.in §The Institute of Mathematical Sciences, HBNI, Chennai, India. saket@imsc.res.in ¶New York University Shanghai, China. jiexue@nyu.edu ‖Ben-Gurion University of the Negev, Beersheba, Israel. meiravze@bgu.ac.il

Uncontrolled Keywords:

Disc graphs; Extended abstracts; Fixed-parameter tractable algorithms; Odd cycle transversals; Parameterized algorithm; Parameterized complexity; Planar graph; Subexponential time; Tree-width; Unit disc graphs

Subjects:

Computer science

Divisions:

Department of Computer Science & Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

16 Jul 2022 11:13

Last Modified:

16 Jul 2022 11:13

URI:

http://raiithold.iith.ac.in/id/eprint/9752