Document Open Access Logo

Path-Contractions, Edge Deletions and Connectivity Preservation

Authors Gregory Gutin, M. S. Ramanujan, Felix Reidl, Magnus Wahlström

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.47.pdf
  • Filesize: 0.63 MB
  • 13 pages

Document Identifiers

Author Details

Gregory Gutin
M. S. Ramanujan
Felix Reidl
Magnus Wahlström

Cite As Get BibTex

Gregory Gutin, M. S. Ramanujan, Felix Reidl, and Magnus Wahlström. Path-Contractions, Edge Deletions and Connectivity Preservation. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.47

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.

Subject Classification

Keywords
  • connectivity
  • strong connectivity
  • vertex deletion
  • arc contraction

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jørgen Bang-Jensen and Gregory Z Gutin. Digraphs: theory, algorithms and applications. Springer Science &Business Media, 2008. Google Scholar
  2. Jørgen Bang-Jensen and Anders Yeo. The minimum spanning strong subdigraph problem is fixed parameter tractable. Discrete Applied Mathematics, 156(15):2924-2929, 2008. Google Scholar
  3. Manu Basavaraju, Fedor V Fomin, Petr Golovach, Pranabendu Misra, MS Ramanujan, and Saket Saurabh. Parameterized algorithms to preserve connectivity. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), pages 800-811. Springer, 2014. Google Scholar
  4. Manu Basavaraju, Pranabendu Misra, M. S. Ramanujan, and Saket Saurabh. On finding highly connected spanning subgraphs. CoRR, abs/1701.02853, 2017. Google Scholar
  5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  6. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM (JACM), 63(4):29:1-29:60, September 2016. Google Scholar
  7. András Frank. Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discrete Math., 5(1):25-53, 1992. Google Scholar
  8. András Frank. Connections in Combinatorial Optimization. Oxford Univ. Press, 2011. Google Scholar
  9. András Frank and Tibor Jordán. Minimal edge-coverings of pairs of sets. J. Comb. Theory, Ser. B, 65(1):73-110, 1995. Google Scholar
  10. Jiong Guo and Johannes Uhlmann. Kernelization and complexity results for connectivity augmentation problems. Networks, 56(2):131-142, 2010. Google Scholar
  11. Gregory Gutin, M. S. Ramanujan, Felix Reidl, and Magnus Wahlström. Path-contractions, edge deletions and connectivity preservation. CoRR, abs/1704.06622, 2017. URL: https://arxiv.org/abs/1704.06622.
  12. Stefan Kratsch. Recent developments in kernelization: A survey. Bulletin of the EATCS, 113, 2014. Google Scholar
  13. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 450-459. IEEE Computer Society, 2012. Google Scholar
  14. Dániel Marx and László A Végh. Fixed-parameter algorithms for minimum-cost edge-connectivity augmentation. ACM Transactions on Algorithms (TALG), 11(4):27, 2015. Google Scholar
  15. Dennis M Moyles and Gerald L Thompson. An algorithm for finding a minimum equivalent graph of a digraph. Journal of the ACM (JACM), 16(3):455-460, 1969. Google Scholar
  16. Hiroshi Nagamochi. An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree. Discrete Applied Mathematics, 126(1):83-113, 2003. 5th Annual International Computing and combinatorics Conference. Google Scholar
  17. László A. Végh. Augmenting undirected node-connectivity by one. SIAM J. Discrete Math., 25(2):695-718, 2011. Google Scholar
  18. T. Watanabe and A. Nakamura. Edge-connectivity augmentation problems. J. Comput. System Sci., 35:96 - 144, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact