Solving Vertex Integrity Faster than $2^n$

Abstract

Vertex Integrity is a classical graph parameter measuring the vulnerability of a network to vertex failures. We settle two fundamental questions concerning its exact exponential complexity. First, we prove that, unless the Exponential Time Hypothesis fails, Vertex Integrity has no $2^{o(n)}{n}^{O(1)}$-time algorithm. Secondly, we give a deterministic exact algorithm running in $O(1.9602^n)$ time and space, improving the straightforward $O(2^n)$ bound.

arXiv comment14 Pages, 1 figure