Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based Radii

Imagine you are a city planner tasked with organizing a neighborhood of houses. In this neighborhood, every house has a Wi-Fi signal (represented by a circle or "disk" around the house).

The Goal: You want the neighborhood to have a specific "personality" or structure (like everyone being in one big chat group, or having distinct, separate cliques).
The Problem: Currently, the Wi-Fi signals are all set to the exact same strength (radius = 1). Because of this fixed strength, some houses that should be connected aren't, and some that shouldn't are.
The Tool: You have a budget of $k$ . With this budget, you can go to up to $k$ houses and adjust their Wi-Fi signal strength. You can make the signal weaker (shrink the circle) or stronger (expand the circle), but you must keep the signal within a specific range (e.g., between 0.5 and 2.0 units).

This paper is about figuring out the best way to use your budget to fix the neighborhood's structure.

The Big Idea: From "One Size Fits All" to "Custom Fitting"

Previous research (by Fomin et al.) looked at a simpler version of this problem. They said: "If you change a signal, you must change all changed signals to the exact same new strength."

Analogy: Imagine you have a box of identical rubber bands. If you stretch one, you have to stretch all of them by the exact same amount.

This paper says: "That's too rigid! In the real world, some sensors need a tiny boost, while others need a huge one."

The New Rule: You can pick a house and set its signal to any strength you want, as long as it stays within your allowed range (e.g., between 0.5 and 2.0). One house might get a signal of 0.6, while its neighbor gets 1.9.

The authors ask: "Is it easy or hard to figure out which houses to tweak and how much to tweak them to get the perfect neighborhood structure?"

The Three Main Discoveries

The authors tested this on three different types of "neighborhood personalities" (graph classes):

1. The "Clubs" (Cluster Graphs)

The Goal: The neighborhood should be split into distinct, tight-knit groups (cliques) where everyone talks to everyone in their group, but no one talks to people outside their group.

The Challenge: This is tricky. Sometimes you need to shrink a signal to break a connection, and other times you need to expand it to make a connection. Because you have a range of options, there are millions of ways to try to fix it.
The Result:
- It's Hard (NP-Hard): If you just want to know if it's possible, it's computationally very difficult for large neighborhoods. It's like trying to solve a massive Sudoku puzzle where the rules change as you play.
- But... It's Manageable (FPT): If your budget ( $k$ ) is small (you can only fix a few houses), there is a clever algorithm that can solve it quickly. The time it takes depends mostly on how small your budget is, not how huge the city is.
- Metaphor: If you only have 3 tools to fix a broken machine, you can figure it out quickly. If you have to fix the whole factory, it's a nightmare.

2. The "Super-Group" (Complete Graphs)

The Goal: Everyone in the neighborhood must be able to talk to everyone else. One giant chat room.

The Strategy: To make everyone connected, you generally want to maximize the signal strength. You make the signals as big as possible (up to your limit) to ensure they overlap.
The Result: This is actually easy (Polynomial Time).
Metaphor: It's like trying to make sure every person in a room can hear the speaker. You just turn the volume up to the max. There's a straightforward, fast recipe to do this.

3. The "Connected Web" (Connected Graphs)

The Goal: The neighborhood must be one single connected piece. You can walk from any house to any other house (even if you have to go through neighbors).

The Result: This is very hard (W[1]-Hard). Even if your budget is small, the problem is so complex that no efficient algorithm is likely to exist.
Metaphor: Imagine trying to connect a scattered set of islands with bridges. Even if you are only allowed to build a few bridges, figuring out which ones to build so the whole archipelago is connected is a nightmare of possibilities. The authors proved that this specific version of the problem is fundamentally difficult, even for computers.

Why Does This Matter?

This isn't just about math puzzles; it's about real-world technology.

Sensor Networks: Think of a forest full of sensors monitoring temperature. Their positions are fixed (you can't move the trees), but you can adjust their transmission range (how far their signal goes).
The Application: If you want the sensors to form a specific network (e.g., "Group A talks to Group A, but not Group B"), this paper tells engineers:
1. Don't try to brute-force it for complex networks (it's too slow).
2. Use smart algorithms if you only need to fix a few sensors.
3. Be careful if you need a fully connected network; it might be impossible to solve efficiently.

Summary in a Nutshell

Old Way: "Change all signals to the exact same new size." (Too rigid).
New Way: "Change each signal to whatever size fits best, within a range." (More realistic).
The Verdict:
- Making a perfectly connected network? Super hard.
- Making tight-knit groups? Hard, but doable if you have a small budget.
- Making one giant group? Easy.

The authors essentially drew a map for engineers, showing which network problems are solvable with a few tweaks and which ones are mathematically impossible to solve quickly.

Here is a detailed technical summary of the paper "Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based Radii" by Thomas Depian and Frank Sommer.

1. Problem Definition

The paper addresses the $\Pi$ -Scaling problem, a generalization of graph modification problems on geometric intersection graphs, specifically Unit Disk Graphs (UDGs).

Input: A set $S$ of $n$ points in the plane (representing centers of unit disks), a radius interval $[r_{min}, r_{max}]$ , and an integer budget $k$ .
Goal: Determine if there exists a subset $T \subseteq S$ $T \subseteq S$ of at most $k$ $k$ points and a radius assignment $r: S \to \mathbb{R}_{>0}$ $r : S \to R_{> 0}$ such that:
1. For all $p \in T$ , $r_{min} \le r(p) \le r_{max}$ .
2. For all $p \in S \setminus T$ , $r(p) = 1$ (the original unit radius).
3. The resulting disk graph $G(S, r)$ belongs to a specific target graph class $\Pi$ .
Context: Previous work by Fomin et al. (ITCS '25) studied a restricted version where all modified disks must be scaled to a single fixed radius $\alpha \neq 1$ . This paper generalizes the model to allow each modified disk to choose a radius independently within an interval, enabling simultaneous shrinking and expanding.

2. Methodology

The authors employ a mix of parameterized complexity analysis, geometric reasoning, and linear programming (LP) to analyze the complexity of $\Pi$ -Scaling for various graph classes.

A. General Framework (XP Membership)

The authors first establish that $\Pi$ -Scaling is in XP (solvable in $n^{f(k)}$ time) for any graph class $\Pi$ recognizable in polynomial time.

Technique: They use a branching strategy to guess the set of scaled disks $T$ and the "target" graph structure.
Geometric Insight: Instead of guessing the exact radius for every disk, they guess the furthest unscaled neighbor ( $far(p)$ ) for each scaled disk $p$ . Due to the geometric nature of disk graphs, knowing the furthest neighbor determines the adjacency to all other unscaled disks (if distance $\le$ distance to $far(p)$ , they intersect).
LP Formulation: Once $T$ and the target adjacency structure $H$ are fixed, the problem reduces to finding valid radii. This is modeled as a Linear Program (ConScal) with variables for radii and constraints ensuring intersections/non-intersections based on Euclidean distances.

B. Fixed-Parameter Tractability (FPT) for Cluster Graphs

For the specific class of Cluster Graphs (graphs with no induced $P_3$ ), the authors design an FPT algorithm (running time $2^{O(k \log k)} \cdot n^{O(1)}$).

Challenge: Cluster graphs require precise radius choices to merge or separate components without creating induced $P_3$ s.
Algorithm: A two-phase branch-and-bound approach:
1. Phase 1: Iteratively identify disks to scale. For each candidate disk $p$ $p$ , the algorithm guesses two critical unscaled neighbors:
  - $far(p)$ : The furthest unscaled disk in the same cluster.
  - $clo(p)$ : The closest unscaled disk in a different cluster.
  - This geometric bounding limits the number of branching choices to $O(k^2)$ , avoiding the exponential blowup of the general XP approach.
2. Phase 2: Resolve adjacencies between the scaled disks themselves and verify the solution using the LP from Section 3.1.

C. Polynomial-Time Algorithm for Complete Graphs

For Complete Graphs, the problem is solvable in polynomial time.

Insight: To make a graph complete, one should always scale disks to the maximum possible radius ( $r_{max}$ ).
Reduction: The problem reduces to finding a Maximum Clique in a specific subgraph of the original unit disk graph. Since Maximum Clique is polynomial-time solvable for UDGs, the entire problem is polynomial.

D. Hardness Results

The paper establishes hardness for other classes:

NP-Hardness for Cluster Graphs: Proven for any fixed rational $r_{min} \le r_{max}$ $r_{min} \leq r_{ma x}$ (except $r_{min}=r_{max}=1$ $r_{min} = r_{ma x} = 1$ ).
- Technique: Reductions from Vertex Cover (for $r_{min} < 1$ ) and Independent Set (for $r_{min} \ge 1$ ).
- Gadgets: The authors construct "heavy $P_3$ s" (clusters of co-located disks) to force specific scaling behaviors. If a disk is not scaled, the heavy $P_3$ remains, violating the cluster property.
W[1]-Hardness for Connected Graphs: Proven when parameterized by $k$ $k$ .
- Technique: Reduction from Grid Tiling With $>$ .
- Construction: A grid of gadgets representing tiles and constraints. Scaled disks represent selected tuples. Connectivity is enforced only if the selected tuples satisfy the strict inequality constraints ( $a > a'$ ). This generalizes previous hardness results where the set of scalable disks was restricted.

3. Key Contributions

Model Generalization: Extended the disk scaling model from a single fixed radius $\alpha$ to an interval $[r_{min}, r_{max}]$ , allowing for more flexible geometric modifications.
Complexity Dichotomy:
- FPT: Solved for Cluster Graphs (improving upon the XP bound).
- Polynomial: Solved for Complete Graphs.
- W[1]-Hard: Proven for Connected Graphs.
- NP-Hard: Proven for Cluster Graphs (when $k$ is part of the input, i.e., non-parameterized).
Algorithmic Techniques:
- Developed a general LP-based framework for verifying radius assignments.
- Introduced a geometric branching strategy based on "furthest" and "closest" neighbors to achieve FPT for cluster graphs.
- Constructed novel heavy disk gadgets to prove NP-hardness for interval-based radii.
Resolution of Open Questions:
- Answered open questions from Fomin et al. regarding the complexity of scaling to Cluster and Complete graphs.
- Showed that the complexity of $\Pi$ -Scaling can differ drastically depending on whether $r_{min} \ge 1$ (expansion) or $r_{max} \le 1$ (shrinking).

4. Results Summary

Target Class $\Pi$	Complexity (Parameterized by $k$ )	Notes
General $\Pi$ (poly-time recognizable)	XP	$2^{O(k^2)} \cdot n^{O(k)}$ via general framework.
Cluster Graphs	FPT	$2^{O(k \log k)} \cdot n^{O(1)}$.
Cluster Graphs (Non-param)	NP-hard	For any fixed $r_{min} \le r_{max}$ (except $1,1$).
Complete Graphs	P	$O(n^{2.5} \log n)$ via reduction to Clique.
Connected Graphs	W[1]-hard	Generalizes previous results; no FPT likely.
Independent Set	W[1]-hard	Follows from known UDG hardness.

5. Significance

This paper significantly advances the understanding of geometric graph modification.

Theoretical Impact: It demonstrates that allowing interval-based radii does not trivially make the problem harder (FPT is still achievable for Cluster graphs) but introduces new geometric constraints that complicate hardness proofs (requiring new gadgets for NP-hardness).
Practical Relevance: The model reflects real-world scenarios in sensor networks where transmission ranges can be dynamically adjusted within a hardware-limited interval, rather than just uniformly expanded or shrunk.
Future Directions: The authors identify open problems, including the existence of a polynomial kernel for Cluster graphs, the NP-containment of the problem, and extensions to non-unit disk graphs and optimization variants (minimizing total radius change).

In conclusion, the paper provides a comprehensive complexity landscape for disk scaling, bridging the gap between abstract graph modification and geometric constraints through rigorous algorithmic design and hardness reductions.