Vertex integrity solved faster than two to the power n time
Solving Vertex Integrity Faster than $2^n$
Data Structures and AlgorithmsDiscrete Mathematics
Summary
Vertex integrity measures how to split a graph by removing some points so that the largest remaining group is small. The authors show that this problem cannot be solved significantly faster than checking all possibilities unless a famous hypothesis is false. They also develop a new algorithm that runs faster than the straightforward method by smartly breaking down the graph and using advanced dynamic programming. This approach improves exact computations on graphs and can also find an optimal splitting set efficiently.
What this means in practice
- •For network designers: Precisely determine critical points to improve robustness by efficiently computing vertex integrity on complex networks.
- •For software engineers: Implement faster exact graph partitioning tools that can identify vulnerable components in software dependency graphs.
A theory result. No direct application yet.
Authors
Sandip Das, Sweta Das, Sk Samim Islam, Ritam Manna Mitra, Aashirwad Mohapatra, Arkaprava Paul
Abstract
The vertex integrity of a graph $G$ is the minimum of $|S|+\max_{C\in\operatorname{cc}(G-S)}|V(C)|$ over all vertex sets $S\subseteq V(G)$, where the maximum is zero if $G-S$ is empty. We study its exact exponential complexity in terms of $n=|V(G)|$. First, we give a reduction from Vertex Cover on subcubic graphs that increases the number of vertices by only a constant factor. Consequently, unless the Exponential Time Hypothesis fails, Vertex Integrity admits no $2^{o(n)}n^{O(1)}$-time algorithm. We also give a deterministic exact algorithm running in $O(1.9602^n)$ time and space, improving on the direct $O^*(2^n)$ algorithm. Its key ingredients are a balanced partition of the components left by an optimal irredundant separator and a subset dynamic program restricted to sets of at most $\lceil 2n/5\rceil$ vertices. An optimal separator can be recovered within the same bounds.