Portal de Periódicos da CAPES

On the Computational Complexity of Vertex Integrity and Component Order Connectivity

2016; Springer Science+Business Media; Volume: 76; Issue: 4 Linguagem: Inglês

10.1007/s00453-016-0127-x

1432-0541

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

Limits and Structures in Graph Theory

The Weighted Vertex Integrity (wVI) problem takes as input an n-vertex graph G, a weight function $$w:V(G)\rightarrow {\mathbb {N}}$$ , and an integer p. The task is to decide if there exists a set $$X\subseteq 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: Result (1) refutes a conjecture by Ray and Deogun (J Comb Math Comb Comput 16:65–73, 1994) and answers an open question by Ray et al. (Ars Comb 79:77–95, 2006). It also complements a result by Kratsch et al. (Discret Appl Math 77(3):259–270, 1997), stating that the unweighted version of the problem can be solved in polynomial time on co-comparability graphs of bounded dimension, provided that an intersection model of the input graph is given as part of the input. An instance of the Weighted Component Order Connectivity (wCOC) problem consists of an n-vertex graph G, a weight function $$w:V(G)\rightarrow {\mathbb {N}}$$ , and two integers k and $$\ell $$ , and the task is to decide if there exists a set $$X\subseteq 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 $$\ell $$ . 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: We also show that result (6) is essentially tight by proving that wCOC cannot be solved in $$2^{o(k \log \ell )}n^{O(1)}$$ time, even when restricted to split graphs, unless the Exponential Time Hypothesis fails.