References & Citations
Computer Science > Data Structures and Algorithms
Title: Parameterized Vertex Integrity Revisited
(Submitted on 15 Feb 2024 (v1), last revised 26 Apr 2024 (this version, v2))
Abstract: Vertex integrity is a graph parameter that measures the connectivity of a graph. Informally, its meaning is that a graph has small vertex integrity if it has a small separator whose removal disconnects the graph into connected components which are themselves also small. Graphs with low vertex integrity are extremely structured; this renders many hard problems tractable and has recently attracted interest in this notion from the parameterized complexity community. In this paper we revisit the NP-complete problem of computing the vertex integrity of a given graph from the point of view of structural parameterizations. We present a number of new results, which also answer some recently posed open questions from the literature. Specifically: We show that unweighted vertex integrity is W[1]-hard parameterized by treedepth; we show that the problem remains W[1]-hard if we parameterize by feedback edge set size (via a reduction from a Bin Packing variant which may be of independent interest); and complementing this we show that the problem is FPT by max-leaf number. Furthermore, for weighted vertex integrity, we show that the problem admits a single-exponential FPT algorithm parameterized by vertex cover or by modular width, the latter result improving upon a previous algorithm which required weights to be polynomially bounded.
Submission history
From: Manolis Vasilakis [view email][v1] Thu, 15 Feb 2024 14:28:01 GMT (204kb,D)
[v2] Fri, 26 Apr 2024 07:07:03 GMT (220kb,D)
Link back to: arXiv, form interface, contact.