2026-07-25T13:34:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20614 2024-08-23T05:50:29Z ddc:004 open_access

Parameterized Vertex Integrity Revisited Hanaka, Tesshu Lampis, Michael Vasilakis, Manolis Yoshiwatari, Kanae Parameterized Complexity Treedepth Vertex Integrity 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 very 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tesshu Hanaka and Michael Lampis and Manolis Vasilakis and Kanae Yoshiwatari 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.58 urn:nbn:de:0030-drops-206141 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.58 eng https://creativecommons.org/licenses/by/4.0/legalcode