Polynomial kernel for 2-Club Cluster Edge Deletion

Given a graph $G=(V,E)$ and an integer $k$ , determine whether there exists an edge set $F\subseteq E$ with $|F|\le k$ such that every connected component of $G-F$ has diameter at most $2$ . The open kernelization question is whether this decision problem, parameterized by $k$ , admits a polynomial kernel: that is, whether there is a polynomial-time algorithm that transforms every instance $(G,k)$ into an equivalent instance $(G',k')$ whose encoding size (in particular, its number of vertices) is bounded by $k^{O(1)}$ .

References

Primary source

arXiv

Additional references

Kernelization of 2-Club Cluster Edge Deletion on Interval Graphs — arXiv

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

A new result gives efficient preprocessing for interval graphs, but the general question of whether this problem has a polynomial-size preprocessing remains open.

The problem asks whether instances can always be reduced to polynomial size in the edge-deletion budget. No proposer or original date is identified in the retrieved sources.

Known results

An earlier preprint leaves the parameterization by the deletion budget $k$ alone unresolved.
For $s=2$ , it claims NP-hardness on split graphs and no polynomial kernel under vertex-cover parameterization unless the stated polynomial-hierarchy collapse occurs.

September 2026 interval-graph kernel

A new preprint claims a polynomial vertex kernel of size $\mathcal{O}(k^5)$ on interval graphs, polynomial-time solvability on unit interval graphs, and NP-hardness on split graphs. These results establish progress on restricted graph classes but do not settle the general-graph kernel question; the claims are not independently verified here.

Current status (as of September 2026): A polynomial kernel is claimed for interval graphs, while the general-graph question remains open and the reported restricted-class results are unverified.

Sources

No solutions have been posted yet.