Path-contractions, edge deletions and connectivity preservation

摘要

We study several problems related to graph modification under connectivity constraints from the perspective of parameterized complexity. In particular, we study (a) (Weighted) Biconnectivity Deletion, where we are tasked with deleting k edges while preserving biconnectivity in an undirected graph, and (b) Path-contraction Preserving Strong Connectivity, where we want to maintain strong connectivity of a digraph while path-contracting k arcs. The parameterized tractability of this last problem was posed in Bang-Jensen and Yeo (2008) [1] as an open question and we answer it here in the negative. On the other hand, we show that preserving (weighted) biconnectivity is fixed-parameter tractable (FPT) and the unweighted case even admits a randomized polynomial kernel. Finally, we show that the most general case of the (unweighted) problem where one would like to preserve ρ-vertex connectivity for any ρ is (non-uniformly) FPT parameterized by k and ρ.