Source-linked AI summary
Kernelization of 2-Club Cluster Edge Deletion on Interval Graphs
Ajinkya Gaikwad
TL;DR
The paper addresses the open question of polynomial kernelization for 2-Club Cluster Edge Deletion by studying structured graph classes. It develops interval-graph reduction rules yielding a polynomial vertex kernel, while also establishing unit-interval solvability and split-graph hardness.
Problem
On general graphs, 2-Club Cluster Edge Deletion is fixed-parameter tractable in k, but whether it admits a polynomial kernel remains open.
Method
The paper applies structural reduction rules based on interval ordering, diameter arguments, and domination relations to kernelize the problem on interval graphs.
Results
The paper proves an O(k^5)-vertex kernel on interval graphs, polynomial-time solvability for every fixed s on unit interval graphs, and NP-hardness for the 2-club case on split graphs.
Takeaways & Limitations
The results separate the computational behavior of bounded-diameter clustering across interval, unit interval, and split graph classes.
Takeaways & Limitations
For interval graphs, it remains open whether 2-Club Cluster Edge Deletion is NP-hard, and extending one reduction rule to arbitrary s remains open.
Abstract
from arXiv · showhide
The \emph{$s$-Club Cluster Edge Deletion} problem asks whether, given a graph $G$ and an integer $k$, one can delete at most $k$ edges so that every remaining connected component has diameter at most~$s$. This generalizes the classical \emph{Cluster Edge Deletion} problem by permitting components of bounded diameter instead of requiring cliques. On general graphs, $2$-Club Cluster Edge Deletion is known to be fixed-parameter tractable when parameterized by $k$, but it remains open whether it admits a polynomial kernel, as posed in~\cite{ABUKHZAM2023113864}. Motivated by this question, we study the problem on interval graphs and obtain a polynomial vertex kernel of size $\mathcal{O}(k^{5})$. As a complementary result, we also show that the \emph{$s$-Club Cluster Edge Deletion} problem is polynomial time solvable on unit interval graphs. We also show that $2$-Club Cluster Edge Deletion is NP-hard even on split graphs.
1 Introduction
The paper places s-Club Cluster Edge Deletion within graph clustering and parameterized complexity, emphasizing the unresolved kernelization question for the 2-club case.
- Cluster Edge Deletion deletes at most k edges so every remaining connected component becomes a clique.
- s-Club Cluster Edge Deletion generalizes this objective by requiring remaining components to have diameter at most a fixed s.
- Each of 2-Club Cluster Vertex Deletion, Edge Deletion, and Editing is NP-complete.
- On general graphs, 2-Club Cluster Edge Deletion is fixed-parameter tractable in k, with an algorithm running in O*(2.692^k) time.
2 Preliminaries
The preliminaries establish graph-theoretic notation and define split and interval graphs, including the interval ordering used throughout the paper.
- The paper defines vertex and edge sets, neighborhoods, induced subgraphs, distances, and graph diameter.
- A split graph has a vertex partition into an independent set I and a clique C, either of which may be empty.
- Split graphs are chordal and perfect, and a split partition can be found in polynomial time.
- An interval graph is the intersection graph of a family of intervals on the real line.
- Interval-graph vertices are ordered by increasing interval left endpoints under a fixed interval representation.
3 On Split Graphs
For split graphs, the problem is polynomial-time solvable when s = 1 or s ≥3, but becomes NP-hard at s = 2.
- When s = 1, s-clubs are exactly cliques, so the problem coincides with Cluster Edge Deletion.
- Cluster Edge Deletion is polynomial-time solvable on split graphs, establishing polynomial-time solvability for the s = 1 case.
- Every connected component of a split graph has diameter at most 3, making the problem polynomial-time solvable on split graphs for s ≥3.
- 2-Club Cluster Edge Deletion is NP-hard on split graphs.
4 On Interval Graphs
The section develops a polynomial kernel for 2-Club Cluster Edge Deletion on interval graphs using structural reduction rules, while distinguishing the s = 2 case from general s. It also establishes polynomial-time solvability on unit interval graphs and leaves the interval-graph complexity question open.
- Kernelization strategy: The kernelization applies reduction rules exploiting interval-graph structure to bound component diameters, component counts, and component sizes.Rules 7–10 apply for all s ≥2, while Rule 11 uses properties specific to 2-clubs.
- Kernelization strategy: A sufficiently large interval-graph component contains either a large independent set or a large clique, enabling two structural reduction branches.The threshold is |V(H)| > (6k + 7)^4, producing a structure of size at least (6k + 7)^2 in polynomial time.
- Kernelization strategy: The independent-set branch deletes a vertex from a long consecutive neighborhood block, while the clique branch uses nested or staircase clique structures.In the staircase case for s = 2, Rule 11 either safely deletes one of two central vertices or detects a no-instance.
- Kernel size: O(k^5) vertices remain in the resulting polynomial-time vertex kernel for 2-Club Cluster Edge Deletion on interval graphs.Once no rule applies, every component has O(k^4) vertices and there are at most k components.
- Unit interval graphs and open questions: For every fixed s ≥1, s-Club Cluster Edge Deletion is solvable in O(n^2) time on unit interval graphs.This provides a polynomial-time result on a restricted subclass, while the problem's NP-hardness status on interval graphs remains open.
B.1 Proof of Theorem 1
The proof reduces Clique on regular graphs to 2-Club Cluster Edge Deletion by constructing a split graph whose feasible deletions encode a sufficiently large clique. The construction is polynomial and establishes NP-hardness on split graphs.
- Reduction construction: The reduction starts from an r-regular Clique instance and sets k′ = r(n − k).The target graph is built from the original graph using subdivision vertices and an auxiliary clique.
- Reduction construction: Each original edge is subdivided, and all subdivision vertices are made into a clique.The original vertices become an independent set, while the subdivision vertices form part of the target clique.
- Reduction construction: A universal auxiliary clique of size k′ + 1 connects the subdivision clique and prevents feasible solutions from separating that structure.The resulting graph has a split partition consisting of the clique C ∪ C′ and the original independent set.
- If direction: Given a clique R of size k, deleting all edges incident to vertices outside R uses exactly k′ deletions and leaves components of diameter at most 2.Vertices outside R become isolated, while R together with the constructed clique remains a 2-club.
- Only if direction: Conversely, any solution with at most k′ deletions yields a clique R of at least k original vertices.The auxiliary construction keeps C ∪ C′ connected; nonadjacent original vertices would violate the diameter bound, and fewer than k retained originals exceed the deletion budget.
- Conclusion: The equivalence is polynomial-time and the constructed instance is a split graph, proving NP-hardness of 2-Club Cluster Edge Deletion on split graphs.The reduction establishes yes-equivalence between the Clique instance and the target instance.
B.2 Proof of Lemma 1
A long shortest path in a connected component cannot remain within diameter s after only k edge deletions, because two surviving vertices remain farther apart than s.
- Proof: If a component already has diameter at most s, removing it preserves the existence of any solution of size at most k.Such a component is already a valid s-club and is disconnected from the rest of the graph.
- Proof: A shortest path of length (s + 1)(k + 1) contains two vertices that remain in one component with distance at least s + 1 after at most k deletions.The path contains enough edges that k deletions cannot separate all relevant vertex pairs.
B.3 Proof of Lemma 2
A solution of budget k can split at most k components whose diameters exceed s, since each such component requires an internal edge deletion.
- Proof: Every remaining component with diameter greater than s requires at least one deleted edge inside that component.Otherwise it would remain a component whose diameter exceeds the target bound.
- Proof: Therefore, a yes-instance can contain at most k components with diameter greater than s before the deletion process.More than k such components would require more than k deletions.
B.4 Proof of Lemma 4
The proof exploits interval representations: a dominating shortest path and consecutive-neighborhood structure force a dense local configuration, while crossing-edge counting supports safe reductions.
- Proof of Lemma 4: A connected interval graph has a shortest path of length equal to its diameter that dominates every vertex.Every vertex is adjacent to at least one path vertex, enabling assignments from the independent set to path vertices.
- Proof of Lemma 4: An independent set of size at least (s + 1)(k + 1)(6k + 7) contains a vertex adjacent to at least 6k + 7 independent-set vertices.This follows by assigning each independent-set vertex to a neighboring path vertex and applying the pigeonhole principle.
- Proof of Lemma 4: The neighbors of that vertex form a consecutive block in the independent-set ordering by left endpoints.Interval geometry ensures that any independent-set intervals between two neighbors also intersect the fixed vertex.
- Proof of Observation 2: For two components of an edge-deleted interval graph, every vertex whose interval meets both component unions is incident to a crossing edge in the deletion set.Connected components have interval unions, and interval intersection with both unions yields an edge crossing between components.
- Proof of Claim 1: If component-union endpoints overlap prescribed independent-set intervals, at least k + 1 distinct crossing edges arise, contradicting a deletion budget of k.The argument uses pairwise-disjoint independent-set intervals to make the crossing edges distinct.
- Proof of Claim 1: A symmetric argument bounds the right endpoint, completing the interval-location claim.The proof applies the same counting argument to intervals on the right side.
B.7 Proof of Claim 2
Claim 2 shows that restoring all edges between two suitable components preserves the s-club property of their union.
- B.7 Proof of Claim 2: Inclusion-minimality ensures no deleted edge has both endpoints within one component of G − F.Restoring such an edge would not merge components and could only decrease internal distances.
- B.7 Proof of Claim 2: Every vertex of Cx is adjacent to u after the relevant edges are restored, giving distance one from u to Cx.This reduces the remaining distance analysis to vertices p distinct from u.
- B.7 Proof of Claim 2: If distG−F(p, u) = s, then p is nonadjacent to u, so its interval lies entirely on one side of Iu.The proof treats the right-sided case and handles the left-sided case symmetrically.
- B.7 Proof of Claim 2: At least one of va, …, va+k belongs to Cu, because otherwise k + 1 distinct incident edges would have to be deleted.A shortest path from p to that vertex has length at most s within Cu.
- B.7 Proof of Claim 2: The interval union along the shortest path intersects Iq between Ivi and Ip, yielding a path from p to q of length at most s.Therefore the merged component Cu ∪ Cx has diameter at most s.
B.8 Proof of Lemma 4
Lemma 4 proves that deleting the designated vertex u preserves the existence of a feasible solution, and that any solution after deletion can be extended back to the original graph.
- B.8 Proof of Lemma 4: The nested clique v1, …, v2k+3 remains in one component after at most k edge deletions.Separating it requires at least 2k + 2 > k deletions.
- B.8 Proof of Lemma 4: For the forward direction, deleting u leaves all other components unchanged and requires showing that C \ {u} remains an s-club.Paths using u are rerouted through a clique vertex adjacent to both neighboring path vertices.
- B.8 Proof of Lemma 4: Replacing x − u − y by x − r − y preserves or shortens relevant paths because r is adjacent to both x and y.The replacement uses a vertex r among v1, …, vk+1.
- B.8 Proof of Lemma 4: In the backward direction, the clique v1, …, v2k+3 \ {u} remains in one component C′ of G′ − F′.All neighbors of u must also belong to C′, since separating one would require k + 1 deletions.
- B.8 Proof of Lemma 4: Adding u back does not merge other components, and every vertex of C′ reaches u within distance at most s.Thus C′ ∪ {u} is an s-club and the original instance is a yes-instance.
B.9 Proof of Lemma 5
Lemma 5 proves the safe removal of a vertex v by handling whether v shares a component with u and by restoring selected edges in the separate-component case.
- B.9 Proof of Lemma 5: The proof chooses an inclusion-minimal solution and distinguishes whether the components containing u and v coincide.These are treated as Case 1 and Case 2, respectively.
- B.9 Proof of Lemma 5: When Cu = Cv, paths using v are rerouted through u because every neighbor of v is also adjacent to u.Replacing x − v − y by x − u − y preserves the path-length bound.
- B.9 Proof of Lemma 5: Thus removing v leaves C \ {v} as an s-club while all other components remain unchanged.The reduced instance is therefore a yes-instance.
- B.9 Proof of Lemma 5: When Cu ≠ Cv, restoring all edges between Cu and Cv merges them into an s-club without increasing the deletion count.The replacement argument can then be applied after u and v lie in one component.
- B.9 Proof of Lemma 5: In the backward direction, components adjacent to v are absorbed into the component containing u before v is restored.The interval-based Claims 1 and 2 apply to the induced graph after deleting v.
- B.9 Proof of Lemma 5: Every vertex in the enlarged component reaches v within distance at most s, so restoring v preserves the s-club property.The proof uses the interval ordering and a vertex among va, …, va+k in the enlarged component.
B.10 Proof of Lemma 5
On unit interval graphs, the proof shows that optimal solutions need not split maximal cliques, enabling a dynamic program over consecutive clique blocks.
- B.10 Proof of Lemma 5: No optimal solution splits a maximal clique in the canonical clique path.A split clique can be assigned wholly to one side without increasing deletions or violating the diameter bound.
- B.10 Proof of Lemma 5: The reconstruction assigns the clique wholly to one side, restores internal edges, and cuts edges outside the selected s-clique window.Choosing the cheaper side ensures the resulting deletion set is no larger.
- B.10 Proof of Lemma 5: Each optimal component corresponds to a consecutive block of at most s maximal cliques in the canonical clique path.The problem becomes partitioning the clique indices into consecutive valid blocks and paying for edges crossing boundaries.
- B.10 Proof of Lemma 5: The cut costs are computable in O(n^2) preprocessing by scanning vertex intervals.These costs count edges crossing a boundary between adjacent clique blocks.
- B.10 Proof of Lemma 5: With fixed s and p = O(n) cliques, the dynamic program runs in O(sn) time after preprocessing.The DP records the minimum deletions needed to partition the first t cliques into valid s-club components.
- B.10 Proof of Lemma 5: Reconstructing the optimal partition yields a minimum edge-deletion set, proving polynomial-time solvability on unit interval graphs.The algorithm outputs the deletion set corresponding to the minimum DP value.