On the Computational Complexity of Vertex Integrity and Component Order Connectivity
| Autor: | Pim van 't Hof, Markus Sortland Dregi, Pål Grønås Drange |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Weight function
Conjecture Computational complexity theory 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Vertex (geometry) Combinatorics 010201 computation theory & mathematics Bounded function 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Intersection model Time complexity Mathematics |
| Zdroj: | Algorithms and Computation ISBN: 9783319130743 ISAAC |
| DOI: | 10.1007/978-3-319-13075-0_23 |
| Popis: | 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: (1) wVI is NP-complete on co-comparability graphs, even if each vertex has weight \(1\); (2) wVI can be solved in \(O(p^{p+1}n)\) time; (3) wVI admits a kernel with at most \(p^3\) vertices. Result (1) refutes a conjecture by Ray and Deogun (J. Combin. Math. Combin. 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. (Discr. Appl. Math. 77: 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|