TL;DR
This paper investigates the computational complexity of modifying graphs to reduce the number of distinct eigenvalues in their adjacency matrices. The authors establish NP-completeness for several variants of this problem, even on restricted graph classes, and provide fixed-parameter tractable (FPT) algorithms for others, offering a comprehensive understanding of the problem's landscape.
What Problem Does This Paper Address?
Graph modification problems are a fundamental area in theoretical computer science, where the goal is to alter a given graph G by removing or adding a minimum number of vertices or edges to satisfy a certain property P. This paper focuses on a specific type of modification: reducing the number of distinct eigenvalues of a graph's adjacency matrix to a small number r. This problem is related to, but distinct from, reducing the rank of the adjacency matrix. The authors explore four variants: vertex deletion (r-EVD), edge deletion (r-EED), edge addition (r-EEA), and edge editing (r-EEE). They aim to map out the computational complexity of these problems, particularly for small values of r, and identify which variants are tractable and under what parameters.
Methods
The paper employs a combination of standard theoretical computer science techniques:
- NP-completeness proofs: Reductions from known NP-complete problems (like Vertex Cover, Independent Set, and 3-PARTITION) to the eigenvalue deletion problems are used to establish their hardness. These reductions often involve constructing specific graph gadgets to simulate the eigenvalue properties.
- Fixed-Parameter Tractability (FPT) algorithms: For some variants, the authors develop algorithms whose runtime is exponential only in a specific parameter (like the solution size k or the maximum degree of the graph), while being polynomial in the size of the input graph. This is achieved through techniques like branching algorithms and kernelization.
- Structural Graph Theory: The paper leverages known structural properties of graphs related to their eigenvalues, such as Lemma 1 (which states that a graph has at most two distinct eigenvalues if and only if it's a disjoint union of equal-sized cliques) and Lemma 2 (relating diameter to the number of distinct eigenvalues).
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The "Uniform Cluster" Connection: The 2-EVD problem is shown to be equivalent to a variant of the "Cluster Vertex Deletion" problem where all resulting clusters must be of the same size. This connection highlights how eigenvalue properties can impose strong structural constraints.
- Complexity Varies with r: The complexity of the eigenvalue deletion problems changes significantly with the parameter r. For instance, 2-EVD is NP-complete on many graph classes, but for r ≥ 3, r-EVD remains NP-complete even on bipartite graphs.
- Edge Addition is Surprisingly Hard: The 2-EEA problem is NP-complete even on very simple graph classes like cluster graphs, forests, and 2-regular graphs, suggesting that adding edges to achieve a specific eigenvalue structure is inherently difficult.
- FPT Algorithms Offer Tractability: Despite the NP-completeness of many variants, the authors demonstrate that some problems are FPT with respect to the solution size k, meaning they can be solved efficiently for small solutions. This is crucial for practical applications where only minor modifications are feasible.
Key Results
- r-EVD: NP-complete for r ≥ 1. Specifically, 2-EVD is NP-complete on triangle-free and 3d-regular graphs for d ≥ 2, and on d-regular graphs for d ≥ 8. For r ≥ 3, r-EVD is NP-complete on bipartite graphs with maximum degree four. 2-EVD admits an FPT algorithm with runtime O(3^k) and is polynomial on forests and d-regular graphs for d ≤ 2.
- r-EEA: NP-complete for r ≥ 2. 2-EEA is NP-complete even on cluster graphs, forests, and 2-regular graphs, and admits a quadratic kernel. r-EEA for r ≥ 3 is also NP-complete.
- r-EED: NP-complete for r ≥ 2. 2-EED admits an FPT algorithm with runtime O(2^k) and is polynomial on triangle-free graphs.
- r-EEE: 2-EEE is NP-complete.
Limitations and Future Work
The authors acknowledge several open questions:
- The complexity of r-EEE for fixed r ≥ 3 remains open.
- The parameterized complexity of 2-EEE in the standard parameter is an open problem.
- Finding polynomial kernels for 2-EVD and 2-EED is an open research direction.
- The authors suggest exploring these problems from the perspective of structural parameters or on directed graphs as interesting avenues for future work.
Summary updated