Path-Contractions, Edge Deletions and Connectivity Preservation. / Gutin, Gregory; Ramanujan, M.S.; Reidl, Felix; Wahlstrom, Magnus.

The 25th Annual European Symposium on Algorithms (ESA 2017). 2017. p. 1-13 47 (LIPICS; Vol. 87).

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

Published

Standard

Path-Contractions, Edge Deletions and Connectivity Preservation. / Gutin, Gregory; Ramanujan, M.S.; Reidl, Felix; Wahlstrom, Magnus.

The 25th Annual European Symposium on Algorithms (ESA 2017). 2017. p. 1-13 47 (LIPICS; Vol. 87).

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

Harvard

Gutin, G, Ramanujan, MS, Reidl, F & Wahlstrom, M 2017, Path-Contractions, Edge Deletions and Connectivity Preservation. in The 25th Annual European Symposium on Algorithms (ESA 2017)., 47, LIPICS, vol. 87, pp. 1-13. https://doi.org/10.4230/LIPIcs.ESA.2017.47

APA

Gutin, G., Ramanujan, M. S., Reidl, F., & Wahlstrom, M. (2017). Path-Contractions, Edge Deletions and Connectivity Preservation. In The 25th Annual European Symposium on Algorithms (ESA 2017) (pp. 1-13). [47] (LIPICS; Vol. 87). https://doi.org/10.4230/LIPIcs.ESA.2017.47

Vancouver

Gutin G, Ramanujan MS, Reidl F, Wahlstrom M. Path-Contractions, Edge Deletions and Connectivity Preservation. In The 25th Annual European Symposium on Algorithms (ESA 2017). 2017. p. 1-13. 47. (LIPICS). https://doi.org/10.4230/LIPIcs.ESA.2017.47

Author

Gutin, Gregory ; Ramanujan, M.S. ; Reidl, Felix ; Wahlstrom, Magnus. / Path-Contractions, Edge Deletions and Connectivity Preservation. The 25th Annual European Symposium on Algorithms (ESA 2017). 2017. pp. 1-13 (LIPICS).

BibTeX

@inproceedings{b7b9c6831de64ad6ae3035b10e0113a8,
title = "Path-Contractions, Edge Deletions and Connectivity Preservation",
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.",
author = "Gregory Gutin and M.S. Ramanujan and Felix Reidl and Magnus Wahlstrom",
year = "2017",
month = sep,
day = "3",
doi = "10.4230/LIPIcs.ESA.2017.47",
language = "English",
isbn = "978-3-95977-049-1",
series = "LIPICS",
pages = "1--13",
booktitle = "The 25th Annual European Symposium on Algorithms (ESA 2017)",

}

RIS

TY - GEN

T1 - Path-Contractions, Edge Deletions and Connectivity Preservation

AU - Gutin, Gregory

AU - Ramanujan, M.S.

AU - Reidl, Felix

AU - Wahlstrom, Magnus

PY - 2017/9/3

Y1 - 2017/9/3

N2 - 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.

AB - 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.

U2 - 10.4230/LIPIcs.ESA.2017.47

DO - 10.4230/LIPIcs.ESA.2017.47

M3 - Conference contribution

SN - 978-3-95977-049-1

T3 - LIPICS

SP - 1

EP - 13

BT - The 25th Annual European Symposium on Algorithms (ESA 2017)

ER -