Bandyapadhyay, Sayan ;
Lochet, William ;
Lokshtanov, Daniel ;
Saurabh, Saket ;
Xue, Jie
True Contraction Decomposition and Almost ETHTight Bipartization for UnitDisk Graphs
Abstract
We prove a structural theorem for unitdisk graphs, which (roughly) states that given a set π of n unit disks inducing a unitdisk graph G_π and a number p β [n], one can partition π into p subsets πβ,β¦ ,π_p such that for every i β [p] and every π' β π_i, the graph obtained from G_π by contracting all edges between the vertices in π_i $1π' admits a tree decomposition in which each bag consists of O(p+π') cliques. Our theorem can be viewed as an analog for unitdisk graphs of the structural theorems for planar graphs and almostembeddable graphs proved very recently by Marx et al. [SODA'22] and Bandyapadhyay et al. [SODA'22].
By applying our structural theorem, we give several new combinatorial and algorithmic results for unitdisk graphs. On the combinatorial side, we obtain the first Contraction Decomposition Theorem (CDT) for unitdisk graphs, resolving an open question in the work Panolan et al. [SODA'19]. On the algorithmic side, we obtain a new FPT algorithm for bipartization (also known as odd cycle transversal) on unitdisk graphs, which runs in 2^{O(βk log k)} β
n^{O(1)} time, where k denotes the solution size. Our algorithm significantly improves the previous slightly subexponentialtime algorithm given by Lokshtanov et al. [SODA'22] (which works more generally for disk graphs) and is almost optimal, as the problem cannot be solved in 2^{o(βk)} β
n^{O(1)} time assuming the ETH.
BibTeX  Entry
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2022.11,
author = {Bandyapadhyay, Sayan and Lochet, William and Lokshtanov, Daniel and Saurabh, Saket and Xue, Jie},
title = {{True Contraction Decomposition and Almost ETHTight Bipartization for UnitDisk Graphs}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {11:111:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772273},
ISSN = {18688969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16019},
URN = {urn:nbn:de:0030drops160190},
doi = {10.4230/LIPIcs.SoCG.2022.11},
annote = {Keywords: unitdisk graphs, tree decomposition, contraction decomposition, bipartization}
}
01.06.2022
Keywords: 

unitdisk graphs, tree decomposition, contraction decomposition, bipartization 
Seminar: 

38th International Symposium on Computational Geometry (SoCG 2022)

Issue date: 

2022 
Date of publication: 

01.06.2022 