License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.11
URN: urn:nbn:de:0030-drops-160190
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16019/
Bandyapadhyay, Sayan ;
Lochet, William ;
Lokshtanov, Daniel ;
Saurabh, Saket ;
Xue, Jie
True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs
Abstract
We prove a structural theorem for unit-disk graphs, which (roughly) states that given a set ? of n unit disks inducing a unit-disk 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 unit-disk graphs of the structural theorems for planar graphs and almost-embeddable 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 unit-disk graphs. On the combinatorial side, we obtain the first Contraction Decomposition Theorem (CDT) for unit-disk 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 unit-disk 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 subexponential-time 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 ETH-Tight Bipartization for Unit-Disk Graphs}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {11:1--11:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-227-3},
ISSN = {1868-8969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16019},
URN = {urn:nbn:de:0030-drops-160190},
doi = {10.4230/LIPIcs.SoCG.2022.11},
annote = {Keywords: unit-disk graphs, tree decomposition, contraction decomposition, bipartization}
}
|
Keywords: |
|
unit-disk graphs, tree decomposition, contraction decomposition, bipartization |
|
Collection: |
|
38th International Symposium on Computational Geometry (SoCG 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.06.2022 |
