Computational Complexity of Integrity

Abstract

The integrity of a graph, $I(G)$, is given by $I(G)=\underset{S}{min}(|S|+m(G–S))$ where $S\subseteq V(G)$ and $m(G–S)$ is the maximum order of the components of $G–S$. It is shown that, for arbitrary graph $G$ and arbitrary integer $k$, the determination of whether $I(G)\le k$ is NP-complete even if $G$ is restricted to be planar. On the other hand, for every positive integer $k$ it is decidable in time $O(n^2)$ whether an arbitrary graph $G$ of order $n$ satisfies $I(G)\le k$. The set of graphs ${\mathcal{G}}_k=\{G|I(G)\le k\}$ is closed under the minor ordering and by the recent results of Robertson and Seymour the set ${\mathcal{O}}_k$ of minimal elements of the complement of ${\mathcal{G}}_k$ is finite. The lower bound $|{\mathcal{O}}_k|\ge (1.7{)}^k$ is established for $k$ large.