Path-contractions, edge deletions and connectivity preservation

2017/04/21 by Gregory Gutin, M. S. Ramanujan, Gutin, Gregory +5 · 1 citation
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.DS

paper · pdf · doi:10.48550/arxiv.1704.06622

arxiv created 2017/04/21 · arxiv updated 2017/04/24

Abstract

We study several problems related to graph modification problems under connectivity constraints from the perspective of parameterized complexity: \sc (Weighted) Biconnectivity Deletion, where we are tasked with deleting~k edges while preserving biconnectivity in an undirected graph, \sc Vertex-deletion Preserving Strong Connectivity, where we want to maintain strong connectivity of a digraph while deleting exactly~k vertices, and \sc Path-contraction Preserving Strong Connectivity, in which the operation of path contraction on arcs is used instead. The parameterized tractability of this last problem was posed by Bang-Jensen and Yeo [DAM 2008] as an open question and we answer it here in the negative: both variants of preserving strong connectivity are \sf W[1]-hard. Preserving biconnectivity, on the other hand, turns out to be fixed parameter tractable and we provide a 2^{O(klog k)} n^O(1)-algorithm that solves \sc Weighted Biconnectivity Deletion. Further, we show that the unweighted case even admits a randomized polynomial kernel. All our results provide further interesting data points for the systematic study of connectivity-preservation constraints in the parameterized setting.

Cited by

• Reducing CMSO to Unbreakable Graphs Cannot be Computable

Related

• Contracting Graphs to Paths and Trees
• Reducing Graph Parameters by Contractions and Deletions
• On the complexity of computing the k-restricted edge-connectivity of a graph
• Parameterized Critical Node Cut Revisited
• Using Edge Contractions and Vertex Deletions to Reduce the Independence Number and the Clique Number