## On the computational complexity of vertex integrity and component order connectivity

*Pål Grønås Drange, Markus Sortland Dregi and Pim van 't Hof*

*Algorithmica*, vol. 76, no. 4, pp. 1181-1202, 2016.

[__DOI__][__Preprint__]

A preliminary version of this paper appeared in the proceedings of ISAAC 2014, the 25th International Symposium on Algorithms and Computation (held on December 15-17, 2014 in Jeonju, Korea), *Lecture Notes in Computer Science*, vol. 8889, pp. 285-297, 2014.

[__DOI__]

### Abstract:

The Weighted Vertex Integrity (wVI) problem takes as input an *n*-vertex graph *G*, a weight function *w* : *V*(*G*) → ℕ, and an integer *p*. The task is to decide if there exists a set *X* ⊆ *V(G)* such that the weight of *X* plus the weight of a heaviest component of *G* - *X* is at most *p*. Among other results, we prove that:

- wVI is NP-complete on co-comparability graphs, even if each vertex has weight 1;
- wVI can be solved in
*O*(*p*^{p+1}*n*) time; - wVI admits a kernel with at most
*p*^{3}vertices.

An instance of the Weighted Component Order Connectivity (wCOC) problem consists of an *n*-vertex graph *G*, a weight function *w* : *V*(*G*) → ℕ, and two integers *k* and ℓ, and the task is to decide if there exists a set *X* ⊆ *V(G)* such that the weight of *X* is at most *k* and the weight of a heaviest component of *G* - *X* is at most ℓ. In some sense, the wCOC problem can be seen as a refined version of the wVI problem. We obtain several classical and parameterized complexity results on the wCOC problem, uncovering interesting similarities and differences between wCOC and wVI. We prove, among other results, that:

- wCOC can be solved in
*O*(min{*k*,ℓ} ·*n*^{3}) time on interval graphs, while the unweighted version can be solved in*O*(*n*^{2}) time on this graph class; - wCOC is W[1]-hard on split graphs when parameterized by
*k*or by ℓ; - wCOC can be solved in 2
^{O(k log ℓ)}·*n*time; - wCOC admits a kernel with at most
*kℓ*(*k*+ ℓ) +*k*vertices.

^{o(k log ℓ)}·

*n*

^{O(1)}time, even when restricted to split graphs, unless the Exponential Time Hypothesis fails.