Parameterized Vertex Integrity Revisited
CoRR(2024)
摘要
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.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要