Kernelization Algorithms for the Eigenvalue Deletion Problems

Given a graph $G=(V,E)$ and an integer k∈ N, we study { 2-Eigenvalue Vertex Deletion} (2-EVD), where the goal is to remove at most k vertices such that the adjacency matrix of the resulting graph has at most 2 eigenvalues. It is known that the adjacency matrix of a graph has at most 2 eigenvalues if and only if the graph is a collection of equal sized cliques. So { 2-Eigenvalue Vertex Deletion} amounts to removing a set of at most k vertices such that the resulting graph is a collection of equal sized cliques. The { 2-Eigenvalue Edge Editing} (2-EEE), { 2-Eigenvalue Edge Deletion} (2-EED) and { 2-Eigenvalue Edge Addition} (2-EEA) problems are defined analogously. We provide a kernel of size O(k³) for { $2$-EVD}. For the problems { $2$-EEE} and { $2$-EED}, we provide kernels of size O(k²). Finally, we provide a linear kernel of size $6k$ for { $2$-EEA}. We thereby resolve three open questions listed by Misra et al. (ISAAC 2023) concerning the complexity of these problems parameterized by the solution size.