CS Paper Radar

Computing Independent Sets of Size Three in Disk Graphs

Anastasiia Tkachenko, Haitao Wang

cs.CG cs.DS ·submitted 2026-11-14 19:53 UTC · v1
published

Abstract

We study the problem of computing an independent set of size three in disk graphs, where vertices correspond to disks in the plane and two vertices are adjacent if their disks intersect. While computing a maximum independent set in disk graphs is NP-hard, the fixed-size case admits more efficient solutions. Given a set of $n$ disks, we present an algorithm to compute an independent set of size three in the disk graph and our algorithm runs in randomized expected $O^*(n^{5/3})$ time, where $O^*$ hides a factor of $n^ε$ for an arbitrarily small $ε> 0$. Our approach introduces a framework based on semi-algebraic range searching and tree-structured biclique partitions, which allows us to group pairs of disjoint disks into canonical subsets and avoid redundant computations. When the centers of the disks are in convex position, we solve the problem in $O(n \log^2 n)$ deterministic time. We also consider the case in which the disks themselves are in convex position, i.e., each disk contributes to the boundary of the convex hull of all disks, and obtain an $O(n \log^2 n)$ time algorithm for this setting as well. Our techniques for these cases are based on geometric properties of disk arrangements. In particular, they rely on new structural lemmas that reduce the problem to efficiently testing certain ordered configurations of disks. Our results improve upon the straightforward quadratic time approach and demonstrate how geometric structures and range searching techniques can be leveraged to solve fixed-size independent set problems in disk graphs more efficiently. To the best of our knowledge, this is the first systematic study of independent sets of size three in disk graphs. Our results show that even this smallest nontrivial case exhibits rich structural properties, especially under convexity assumptions.

Comment
To appear in WALCOM 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Approximating Independent Sets Using Additive Combinatorics

cs.DS cs.CCmath.CO ·2026-10-18 ·Shachar Lovett
published similarity 0.69
Abstract

We give a deterministic quasi-polynomial time algorithm for approximating the largest independent set in a graph. We show that if an $N$-vertex graph contains an independent set of size $2^{-t} N$, then we can find an independent set of size $2^t$ in quasi-polynomial time, for all $t$ up to a constant factor of $(\log N)^{1/3}$. This gives an approximation factor of $N / \exp((\log N)^{1/3})$, which has the same shape as known hardness results for quasi-polynomial time algorithms, up to a different exponent of the logarithm. The algorithm builds on a structural principle: a graph containing a large independent set must also contain a large sparse structured set, and such a set can be found efficiently. A greedy algorithm then extracts an independent set from it. Our proof draws on tools in additive combinatorics, in particular spreadness and sifting, to obtain the combinatorial structural results. We then convert these to efficient algorithms using pseudo-marginals obtained by semidefinite programming.

0.60

A Linear-Size Well-Separated Pair Decomposition for Unit Disk Graphs

cs.CG ·2026-11-17 ·Jie Gao
similarity 0.67
Abstract · 8 pages, 1 figure

Given a metric space $(X, d)$ a $c$-well separated pair decomposition (WSPD) is a collection of `dumbbell' pairs of subsets $(A, B)$, $A, B\subseteq X$, where the distance between the two sets is at least $c$ times the diameter of each set and every pair of points in $X$ is covered by one such pair. It is known that for a weighted unit disk graph metric of $n$ points, there is a WSPD of size $O(n\log n)$. But it is open whether this bound can be improved to $O(n)$. In this note, we answer this question affirmatively and provide an algorithm that yields a linear-size WSPD for unit disk graphs.

0.32

Fixed-Radius Neighbourhoods in Three-Dimensional Unit-Cube Graphs

cs.CG math.CO ·2026-11-04 ·Guangjian Zhang
theory similarity 0.66
Abstract · 30 pages

We prove Conjecture 4 of Chan, Chang, Gao, Kisfaludi-Bak, Le, and Zheng (SoCG 2026): for every fixed integer $r\ge0$, the radius-$r$ neighbourhoods of a unit-cube graph in $\mathbb{R}^3$ have bounded VC-dimension. Our bound is $2^{2^{O(r)}}$, independent of the number of vertices. The main ingredient is a VC-dimension bound for reachability through arbitrary fixed-length sequences of three-dimensional generalized dominance relations. Its proof uses groups ordered in two coordinates, with neighbouring groups acting as barriers that preserve this invariant when one layer is removed. Combining these bounds with the existing interval-representation framework, we obtain a Las Vegas algorithm that, for every fixed integer $Δ\ge1$, decides whether a graph given by $n$ cube centres has diameter at most $Δ$ in expected $O_Δ(n^{2-\varepsilon_Δ})$ time, for an explicit constant $\varepsilon_Δ>0$. Finally, for every integer $r\ge7$, we construct unit-cube graphs with rational centres whose radius-$r$ neighbourhoods have VC-dimension $Ω(r^3)$.

0.27

A Well-Separated Pair Decomposition of Linear Size for Unit-Disk Graphs

cs.CG math.CO ·2026-11-18 ·Mark de Berg, Joachim Gudmundsson, Sampson Wong
theory similarity 0.65
Abstract

We prove that every connected Euclidean-weighted unit-disk graph on $n$ vertices has a $(1/\varepsilon)$-well-separated pair decomposition of size $O(n\varepsilon^{-2}\log(1/\varepsilon))$. This resolves an open problem posed by Gao and Zhang in 2003. We also show that this bound is tight: there are connected unit-disk graphs for which any $(1/\varepsilon)$-well-separated pair decomposition has size $Ω(n\varepsilon^{-2}\log (1/\varepsilon))$.

0.23

Max Weight Independent Set in graphs with no long claws nor large induced bicliques

cs.DS ·2026-10-30 ·Maria Chudnovsky, Paweł Rzążewski
similarity 0.64
Abstract

The complexity of Max Weight Independent Set (MWIS) in graphs excluding a fixed subdivided claw is one of the central open problems in algorithmic graph theory. We show that MWIS can be solved in polynomial time in graphs excluding a fixed subdivided claw and a fixed biclique as an induced subgraph. This strengthens a result of Abrishami, Chudnovsky, Dibek, Pilipczuk, and Rzążewski [ACM TALG 2026] who showed an analogous result, but under a stronger assumption that some biclique is excluded as a subgraph.

0.19

Independent Set Discovery on Biclique-Free Graphs Is Fixed-Parameter Tractable

cs.DS ·2026-08-19 ·Chenghua Liu, Boning Meng
similarity 0.63
Abstract

\textnormal{\textsc{Independent Set Discovery}} asks whether a configuration of $k$ tokens on distinct vertices can be transformed into an independent $k$-set by a sequence of token slides, each moving one token to an unoccupied neighbor; only the terminal configuration must be independent. \textnormal{\textsc{Independent Set Discovery}} is a central problem in solution discovery: its target is not prescribed and must be chosen together with the token movements needed to reach it. Fellows et al. proved it FPT in $k$ on every fixed bounded-degeneracy class and every nowhere-dense class, leaving the biclique-free case open. The biclique-free setting lies substantially beyond both regimes: biclique-free classes can have unbounded degeneracy and even be somewhere dense. We resolve the open problem affirmatively. Given an $n$-vertex, $m$-edge graph promised to be $K_{d,d}$-free and an initial $k$-token configuration, our deterministic algorithm computes the minimum number of slides and, in time $2^{O(dk\log k)}(n+m)^{O(1)}$, returns an optimal independent target and a shortest collision-free slide sequence or certifies that no independent target is reachable. Thus the problem is FPT in $k$ for every fixed $d$ and uniformly FPT in $k+d$. The proof combines an exact minimum-cost assignment characterization of token movement with local branching on bounded, cost-relevant \emph{cheap prefixes} of candidate lists. The method also yields an exact FPT algorithm for weighted independent transversals on $K_{d,d}$-free graphs with overlapping candidate sets, direct exact FPT algorithms for both problems on bounded-degeneracy graphs, an edge-count-sensitive XP algorithm, sharper bounds for bounded $s$-codegree and unbalanced biclique exclusion, and an exact extension to weighted movement on a separate directed graph.

0.20

Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs

cs.DM math.CO ·2026-10-01 ·Gautam K. Das, Kamal Santra
similarity 0.62
Abstract

An edge open packing is a set of edges whose endpoints induce a disjoint union of stars. We study the problem of finding a maximum edge open packing in AT-free, chordal, and convex bipartite graphs. For AT-free graphs, we use the oriented star-conflict graph $A_G$, introduced by Das and Santra, for which $ρ_e^o(G)=α(A_G)$, and prove that $A_G$ is AT-free whenever $G$ is AT-free. Consequently, a known maximum independent set algorithm for AT-free graphs yields an $O(n^2+m^4)$-time algorithm for Maximum Edge Open Packing, where $n$ and $m$ denote the numbers of vertices and edges of $G$, respectively. For chordal graphs, we develop an $O(n^4)$-time dynamic programming algorithm over a nice tree decomposition derived from a clique tree, exploiting the structural fact that the endpoint set of an edge open packing intersects every clique in at most two vertices. Finally, for convex bipartite graphs, we obtain an $O(n^4)$-time dynamic programming algorithm based on two boundary indices that separate consecutive star components. This result extends the previously known algorithm for biconvex bipartite graphs and, in particular, provides an improved explicit running-time bound for that class.

0.07

Deterministic Distance Selection in $O(n^{4/3})$ Time

cs.CG cs.DS ·2026-10-07 ·Haitao Wang
top venue similarity 0.62
Abstract · To appear in SODA 2027

Let $P$ be a set of $n$ points in the plane. Given an integer $K$ with $1\le K\le {n\choose 2}$, the distance selection problem asks for the $K$-th smallest distance among all pairwise distances of the points of $P$. The problem has been studied extensively over the past four decades. Recently, Chan and Zheng (2023) gave a randomized algorithm with $O(n^{4/3})$ expected running time, while the best known deterministic algorithm runs in $O(n^{4/3}\log n)$ time. In this paper, we present a deterministic $O(n^{4/3})$-time algorithm for the problem, matching the best known randomized complexity. We also consider the more general bichromatic version of the problem, where two point sets $A$ and $B$ are given, with $m=|A|$ and $n=|B|$, and the goal is to find the $K$-th smallest distance among the $mn$ distances between points of $A$ and points of $B$. For this problem, the best previously known algorithm runs in $O((m\log n+n\log m+m^{2/3}n^{2/3})\log(m+n))$ time. We present a new deterministic algorithm with running time $O(m\log^2 n+n\log^2 m+m^{2/3}n^{2/3})$.

0.41