True contraction decomposition and almost eth-tight bipartization for unit-disk graphs
ACM Transactions on Algorithms, 2024•dl.acm.org
We prove a structural theorem for unit-disk graphs, which (roughly) states that given a set of
unit disks inducing a unit-disk graph and a number, one can partition into subsets such that
for every and every, the graph obtained from by contracting all edges between the vertices in
admits a tree decomposition in which each bag consists of 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 recently by Marx et al.[SODA'22] and Bandyapadhyay et …
unit disks inducing a unit-disk graph and a number, one can partition into subsets such that
for every and every, the graph obtained from by contracting all edges between the vertices in
admits a tree decomposition in which each bag consists of 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 recently by Marx et al.[SODA'22] and Bandyapadhyay et …
We prove a structural theorem for unit-disk graphs, which (roughly) states that given a set of unit disks inducing a unit-disk graph and a number , one can partition into subsets such that for every and every , the graph obtained from by contracting all edges between the vertices in admits a tree decomposition in which each bag consists of 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 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 for unit-disk graphs, resolving an open question in the work by Panolan et al. [SODA ’19]. On the algorithmic side, we obtain a new algorithm for bipartization (also known as odd cycle transversal) on unit-disk graphs, which runs in time, where denotes the solution size. Our algorithm significantly improves the previous slightly subexponential-time algorithm given by Lokshtanov et al. [SODA ’22] which runs in time. We also show that the problem cannot be solved in time assuming the Exponential Time Hypothesis, which implies that our algorithm is almost optimal.

Showing the best result for this search. See all results