Kernelization of 2-Club Cluster Edge Deletion on Interval Graphs

• Cluster Edge Deletion deletes at most k edges so every remaining connected component becomes a clique.Source: §1 · p. 1
• s-Club Cluster Edge Deletion generalizes this objective by requiring remaining components to have diameter at most a fixed s.Source: §1 · p. 1
• Each of 2-Club Cluster Vertex Deletion, Edge Deletion, and Editing is NP-complete.Source: §1 · p. 2
• On general graphs, 2-Club Cluster Edge Deletion is fixed-parameter tractable in k, with an algorithm running in O*(2.692^k) time.Source: §1 · p. 2

• The paper defines vertex and edge sets, neighborhoods, induced subgraphs, distances, and graph diameter.Source: §2 · p. 2
• A split graph has a vertex partition into an independent set I and a clique C, either of which may be empty.Source: §2 · p. 2
• Split graphs are chordal and perfect, and a split partition can be found in polynomial time.Source: §2 · p. 2
• An interval graph is the intersection graph of a family of intervals on the real line.Source: §2 · p. 2
• Interval-graph vertices are ordered by increasing interval left endpoints under a fixed interval representation.Source: §2 · p. 2

• When s = 1, s-clubs are exactly cliques, so the problem coincides with Cluster Edge Deletion.Source: §3 · p. 3
• Cluster Edge Deletion is polynomial-time solvable on split graphs, establishing polynomial-time solvability for the s = 1 case.Source: §3 · p. 3
• Every connected component of a split graph has diameter at most 3, making the problem polynomial-time solvable on split graphs for s ≥3.Source: §3 · p. 3
• 2-Club Cluster Edge Deletion is NP-hard on split graphs.Source: §3 · p. 3

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.Source: §4 · p. 3, §4.1 · p. 4
• 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.Source: §4.1 · p. 4, §4.2 · p. 5
• 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.Source: §4.1 · pp. 4–5

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.Source: §4.1 · p. 5, §4.2 · p. 12

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.Source: §4 · pp. 3–4, §4.2 · p. 12

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.Source: §B.1 · p. 16
• 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.Source: §B.1 · p. 16
• 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.Source: §B.1 · p. 16

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.Source: §B.1 · pp. 16–17

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.Source: §B.1 · p. 17

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.Source: §B.1 · p. 17

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.Source: §B.2 · p. 17
• 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.Source: §B.2 · p. 17

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.Source: §B.3 · p. 17
• 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.Source: §B.3 · p. 17

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.Source: §B.4 · p. 18
• 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.Source: §B.4 · p. 18
• 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.Source: §B.4 · p. 18

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.Source: §B.5 · p. 18

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.Source: §B.6 · pp. 18–19
• 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.Source: §B.6 · p. 19

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.Source: §B.7 · p. 19
• 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.Source: §B.7 · p. 19
• 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.Source: §B.7 · pp. 19–20
• 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.Source: §B.7 · p. 20
• 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.Source: §B.7 · p. 20

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.Source: §B.8 · p. 20
• 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.Source: §B.8 · p. 21
• 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.Source: §B.8 · p. 21
• 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.Source: §B.8 · p. 21
• 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.Source: §B.8 · p. 22

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.Source: §B.9 · pp. 22–23
• 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.Source: §B.9 · pp. 22–23
• Thus removing v leaves C \ {v} as an s-club while all other components remain unchanged.The reduced instance is therefore a yes-instance.Source: §B.9 · p. 23
• 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.Source: §B.9 · p. 23
• 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.Source: §B.9 · p. 23
• 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.Source: §B.9 · pp. 23–24

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.Source: §B.10 · pp. 24–25
• 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.Source: §B.10 · p. 25
• 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.Source: §B.10 · p. 25
• 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.Source: §B.10 · p. 25
• 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.Source: §B.10 · pp. 25–26
• 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.Source: §B.10 · p. 26