View PDF HTML (experimental)

Abstract:For a fixed graph class $\Pi$, the goal of $\Pi$-Modification is to transform an input graph $G$ into a graph $H\in\Pi$ using at most $k$ modifications. Vertex and edge deletions are common operations, and their (parameterized) complexity for various $\Pi$ is well-studied. Classic graph modification operations such as edge deletion do not consider the geometric nature of intersection graphs such as (unit) disk graphs. This led Fomin et al. [ITCS' 25] to introduce scaling as a geometric graph modification operation for unit disk graphs: For a given radius $r$, each modified disk will be rescaled to radius $r$. In this paper, we generalize their model by allowing rescaled disks to choose a radius within a given interval $[r_{\min}, r_{\max}]$ and study the (parameterized) complexity (with respect to $k$) of the corresponding problem $\Pi$-Scaling. We show that $\Pi$-Scaling is in XP for every graph class $\Pi$ that can be recognized in polynomial time. Furthermore, we show that $\Pi$-Scaling: (1) is NP-hard and FPT for cluster graphs, (2) can be solved in polynomial time for complete graphs, and (3) is W[1]-hard for connected graphs. In particular, (1) and (2) answer open questions of Fomin et al. and (3) generalizes the hardness result for their variant where the set of scalable disks is restricted.

Submission history

From: Thomas Depian [view email]
[v1] Thu, 5 Mar 2026 16:39:19 UTC (690 KB)
[v2] Thu, 13 Aug 2026 13:47:06 UTC (696 KB)