Source-linked AI summary
On the Computational Complexity of Vertex Integrity and Component Order Connectivity
Pål Grønås Drange, Markus Sortland Dregi, Pim van 't Hof
TL;DR
The paper asks how weighted vertex integrity and weighted component order connectivity behave computationally across graph classes and parameterizations. It develops hardness proofs, parameterized algorithms, kernels, and interval-graph algorithms, showing both strong tractability results and tight lower bounds. In particular, wVI is NP-complete on co-comparability graphs, while wCOC has a 2^{O(k log ℓ)}n algorithm and matching ETH-based lower-bound exponent.
Problem
The paper addresses the computational complexity of weighted vertex integrity and the less-studied weighted component order connectivity problem across graph classes and parameters.
Source: §1 · pp. 1–2Method
The paper uses complexity reductions and develops graph-class algorithms, parameterized algorithms, and kernelization procedures for wVI and wCOC.
Source: §1 · pp. 2–3Results
wVI is NP-complete on co-comparability graphs, while wCOC has interval-graph algorithms, a 2^{O(k log ℓ)}n algorithm, and a kernel with at most kℓ(k+ℓ)+k vertices.
Source: §1 · pp. 2–3Takeaways & Limitations
The results distinguish graph classes and parameterizations where these vulnerability problems are tractable from settings where hardness persists.
Source: §1 · pp. 2–3For wCOC, the 2^{O(k log ℓ)}n running time is essentially tight: a 2^{o(k log ℓ)}n^{O(1)} algorithm would imply failure of ETH.
Source: §1 · p. 3, §5 · p. 15
Abstract
from arXiv · showhide
The Weighted Vertex Integrity (wVI) problem takes as input an $n$-vertex graph $G$, a weight function $w:V(G)\to\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 and answers an open question by Ray et al. It also complements a result by Kratsch et al., 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)\to \mathbb{N}$, and two integers $k$ and $l$, 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 $l$. In some sense, the wCOC problem can be seen as a refined version of the wVI problem. We prove, among other results, that: (4) wCOC can be solved in $O(\min\{k,l\}\cdot n^3)$ time on interval graphs, while the unweighted version can be solved in $O(n^2)$ time on this graph class; (5) wCOC is W[1]-hard on split graphs when parameterized by $k$ or by $l$; (6) wCOC can be solved in $2^{O(k\log l)} n$ time; (7) wCOC admits a kernel with at most $kl(k+l)+k$ vertices. We also show that result (6) is essentially tight by proving that wCOC cannot be solved in $2^{o(k \log l)}n^{O(1)}$ time, unless the ETH fails.
1 Introduction
The paper studies weighted vertex integrity and weighted component order connectivity, establishing new hardness, parameterized, kernelization, and graph-class algorithmic results.
Component Order Connectivity
- wCOC separates deletion weight from residual component weight, refining wVI by imposing independent bounds k and ℓ.The problem asks whether deleting a set of weight at most k leaves every component with weight at most ℓ.Source: §1 · p. 2
Vertex Integrity
- wVI is NP-complete on co-bipartite, and therefore co-comparability, graphs, refuting Ray and Deogun’s conjecture and answering Ray et al.’s open question.This contrasts with polynomial-time results for unweighted VI on bounded-dimension co-comparability graphs when an intersection model is provided.Source: §1 · p. 2
- wVI is solvable in O(p^{p+1}n) time and has a kernel with at most p^3 vertices, each of weight at most p.These results strengthen the earlier O(p^{3p}n) algorithm for unweighted VI.Source: §1 · p. 3
Component Order Connectivity
- On interval graphs, wCOC is solvable in O(min{k, ℓ} · n^3) time, while unweighted COC is solvable in O(n^2) time.The unweighted algorithm improves the O(n^3)-time bound implied by earlier results.Source: §1 · p. 3
Parameterized Complexity
- wCOC is W[1]-hard on split graphs for parameter k or ℓ, but is fixed-parameter tractable for k+ℓ in 2^{O(k log ℓ)}n time.Both COC and wCOC are para-NP-hard when parameterized by ℓ, since COC equals Vertex Cover when ℓ=1.Source: §1 · p. 3
- wCOC has a kernel with at most kℓ(k+ℓ)+k vertices, and no 2^{o(k log ℓ)}n^{O(1)} algorithm exists unless ETH fails.The lower bound makes the stated parameterized running time essentially tight.Source: §1 · p. 3
2 Preliminaries
The preliminaries define the graph measures, decision problems, parameterized-complexity terminology, and graph classes used throughout the paper.
Conventions
- The paper considers finite, undirected, simple graphs and treats unqualified NP-completeness as strong NP-completeness.This convention applies to weighted problems unless explicitly stated otherwise.Source: §2 · p. 3
Problem Definitions
- Weighted vertex integrity minimizes w(X)+wcc(G−X), where wcc(G−X) is the weight of a heaviest remaining component.A set attaining this minimum is called an ι-set.Source: §2 · p. 4
- wVI asks whether weighted vertex integrity is at most p, while wCOC asks whether some deletion set has weight at most k and residual component weight at most ℓ.Their unweighted versions are VI and COC, obtained by assigning every vertex weight 1.Source: §2 · p. 4
Graph Classes
- Split graphs partition into a clique and an independent set, interval graphs are intersection graphs of intervals, and co-comparability graphs are complements of comparability graphs.Comparability graphs admit transitive orientations; co-bipartite graphs and interval graphs are subclasses of co-comparability graphs.Source: §2 · p. 4
Parameterized Complexity
- A parameterized problem is fixed-parameter tractable when it runs in f(k)|x|^{O(1)} time, and it has a kernel when equivalent instances can be reduced to size bounded by a function of k.A polynomial kernel uses a polynomial function of the parameter as the size bound.Source: §2 · p. 4
3 Vertex Integrity
This section establishes hardness results for Vertex Integrity and Weighted Vertex Integrity on increasingly broad graph classes, then gives fixed-parameter and kernelization algorithms for wVI.
Hardness results
- Vertex Integrity is NP-complete on co-bipartite graphs, strengthening the hardness boundary beyond the previously studied graph classes.The result also shows that neither arbitrarily many asteroidal triples nor induced five-vertex paths are necessary for NP-completeness.Source: §3 · pp. 4–5
Structural lemmas
- An optimal integrity set can be chosen without simplicial vertices, enabling the hardness reductions to restrict attention to clique-side vertices in incidence split graphs.Removing a simplicial vertex from an integrity set preserves optimality by offsetting its weight against the resulting component weight.Source: §3 · p. 5
Hardness results
- Weighted Vertex Integrity is NP-complete on split graphs via a reduction from Clique using incidence split graphs and an auxiliary weighted vertex.The construction assigns unit weights to the incidence split graph and a larger weight to the added isolated vertex.Source: §3 · pp. 5–6
- Vertex Integrity is NP-complete on chordal graphs, despite being solvable in linear time on split graphs.The chordal-graph reduction modifies the split-graph construction by replacing the isolated weighted vertex with a clique.Source: §3 · p. 6
Parameterized algorithm
- Weighted Vertex Integrity is solvable in O(p^(p+1)n) time by branching on a connected set of at most p+1 vertices whose weight exceeds p.The search tree has depth at most p and O(p^p) nodes after rejecting instances with too many edges.Source: §3 · pp. 6–7
Kernelization
- Weighted Vertex Integrity admits a kernel with at most p^3 vertices, each of weight at most p.The reduction rules retain only the p+1 heaviest components and force deletion of vertices whose closed neighborhoods exceed weight p.Source: §3 · pp. 7–8
- The kernel bound follows by bounding the solution-set size, the number of surviving components, and the size of each component after exhaustive reductions.If the solution set is nonempty, at most p^2+p components remain relevant, each containing at most p−|X| vertices.Source: §3 · pp. 7–8
4 Component Order Connectivity
This section investigates the complexity of Component Order Connectivity and its weighted variant, covering hardness results, interval-graph algorithms, parameterized algorithms, ETH-based lower bounds, and kernelization.
Hardness results
- Weighted Component Order Connectivity is weakly NP-complete on complete graphs via a reduction from Partition.The construction assigns each vertex an integer weight from the Partition instance, with equal deletion and remaining-component weight encoding an equal partition.Source: §4 · p. 8
- Component Order Connectivity is NP-complete on split graphs via a reduction from Clique.The reduction uses the split incidence graph and preserves yes-instances between Clique and Component Order Connectivity.Source: §4 · p. 8
Algorithms on interval graphs
- Weighted Component Order Connectivity can be solved in O(min{k, l} n^3) time on interval graphs.The algorithm uses a clique path, minimal separators, dynamic programming, and a subset-sum-based subroutine; its correctness is established by Lemma 4.1.Source: §4 · pp. 9–11
- The unweighted Component Order Connectivity problem can be solved in O(n^2) time on interval graphs.The faster algorithm replaces weighted subset selection with greedy deletion by cardinality and precomputes the required separator-intersection values.Source: §4 · pp. 11–12
Parameterized complexity
- Component Order Connectivity is W[1]-hard on split graphs when parameterized by k or by l.Hardness for k follows from the Clique reduction, while hardness for l uses a modified split-graph construction whose deletion sets encode cliques.Source: §4 · pp. 12–13
4 Component Order Connectivity
- The hardness construction uses an incidence split graph, where solutions correspond to cliques in the original graph and the constructed parameter satisfies ℓ ≤ k^4.This transfers the k × k Clique lower bound of 2^{o(k log k)} under ETH to Component Order Connectivity.Source: §4 · pp. 13–14
- Weighted Component Order Connectivity is solvable in O(ℓ^k(k + ℓ)n) = 2^{O(k log ℓ)}n time.The algorithm branches on a connected set of at most ℓ + 1 vertices whose deletion is necessary, yielding depth at most k.Source: §4 · p. 13
- Unless ETH fails, Component Order Connectivity has no 2^{o(k log ℓ)}n^{O(1)}-time algorithm, even on split graphs with unit vertex weights.The lower bound follows by reducing k × k Clique through incidence split graphs with ℓ ≤ k^4.Source: §4 · p. 14
- Weighted Component Order Connectivity admits a kernel with at most kℓ(k + ℓ) + k vertices, each of weight at most k + ℓ.The kernel applies neighborhood-weight and small-component reduction rules before bounding the remaining components and solution vertices.Source: §4 · p. 14
5 Concluding Remarks
The paper establishes a conditional lower bound for Component Order Connectivity and leaves stronger single-exponential algorithms as open questions.
5 Concluding Remarks
- Unless ETH fails, Component Order Connectivity has no 2^{o(k log ℓ)}n^{O(1)}-time algorithm.The paper asks whether a c^{k+ℓ}n^{O(1)} algorithm might nevertheless exist.Source: §5 · p. 15