Computational Complexity of Integrity

The integrity of a graph, \(I(G)\), is given by \(I(G) = \min_{S} (|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) \leq 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) \leq k\). The set of graphs \(\mathcal{G}_k = \{G | I(G) \leq 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| \geq (1.7)^k\) is established for \(k\) large.