Parameterized Vertex Integrity Revisited
<|reference_start|>Parameterized Vertex Integrity Revisited: 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.<|reference_end|>
@article{hanaka2024parameterized,
    title={Parameterized Vertex Integrity Revisited},
    author={Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, and Kanae
  Yoshiwatari},
    journal={arXiv preprint arXiv:2402.09971},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.09971},
    primaryClass={cs.DS cs.CC}
}