Path-Contractions, Edge Deletions and Connectivity Preservation

Gregory Gutin, M.S. Ramanujan, Felix Reidl, Magnus Wahlstrom

Research output: Chapter in Book/Report/Conference proceedingConference contribution

55 Downloads (Pure)

Abstract

We study several problems related to graph modification problems under connectivity constraints from the perspective of parameterized complexity: (Weighted) Biconnectivity Deletion, where we are tasked with deleting k edges while preserving biconnectivity in an undirected graph, Vertexdeletion Preserving Strong Connectivity, where we want to maintain strong connectivity of a digraph while deleting exactly k vertices, and 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 in [Bang-Jensen and Yeo, Discrete Applied Math 2008] as an open question and we answer it here in the negative: both variants of preserving strong connectivity are W[1]-hard. Preserving biconnectivity, on the other hand, turns out to be fixed parameter tractable (FPT) and we provide an FPT algorithm that solves 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 connectivitypreservation constraints in the parameterized setting.
Original languageEnglish
Title of host publicationThe 25th Annual European Symposium on Algorithms (ESA 2017)
Pages1-13
Number of pages13
DOIs
Publication statusPublished - 3 Sept 2017

Publication series

NameLIPICS
Volume87
ISSN (Print)1868-8969

Cite this