License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.17
URN: urn:nbn:de:0030-drops-176690
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17669/
Cairo, Massimo ;
Khan, Shahbaz ;
Rizzi, Romeo ;
Schmidt, Sebastian ;
Tomescu, Alexandru I. ;
Zirondelli, Elia C.
Cut Paths and Their Remainder Structure, with Applications
Abstract
In a strongly connected graph G = (V,E), a cut arc (also called strong bridge) is an arc e ∈ E whose removal makes the graph no longer strongly connected. Equivalently, there exist u,v ∈ V, such that all u-v walks contain e. Cut arcs are a fundamental graph-theoretic notion, with countless applications, especially in reachability problems.
In this paper we initiate the study of cut paths, as a generalisation of cut arcs, which we naturally define as those paths P for which there exist u,v ∈ V, such that all u-v walks contain P as subwalk. We first prove various properties of cut paths and define their remainder structures, which we use to present a simple O(m)-time verification algorithm for a cut path (|V| = n, |E| = m).
Secondly, we apply cut paths and their remainder structures to improve several reachability problems from bioinformatics, as follows. A walk is called safe if it is a subwalk of every node-covering closed walk of a strongly connected graph. Multi-safety is defined analogously, by considering node-covering sets of closed walks instead. We show that cut paths provide simple O(m)-time algorithms verifying if a walk is safe or multi-safe. For multi-safety, we present the first linear time algorithm, while for safety, we present a simple algorithm where the state-of-the-art employed complex data structures. Finally we show that the simultaneous computation of remainder structures of all subwalks of a cut path can be performed in linear time, since they are related in a structured way. These properties yield an O(mn)-time algorithm outputting all maximal multi-safe walks, improving over the state-of-the-art algorithm running in time O(m²+n³).
The results of this paper only scratch the surface in the study of cut paths, and we believe a rich structure of a graph can be revealed, considering the perspective of a path, instead of just an arc.
BibTeX - Entry
@InProceedings{cairo_et_al:LIPIcs.STACS.2023.17,
author = {Cairo, Massimo and Khan, Shahbaz and Rizzi, Romeo and Schmidt, Sebastian and Tomescu, Alexandru I. and Zirondelli, Elia C.},
title = {{Cut Paths and Their Remainder Structure, with Applications}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {17:1--17:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-266-2},
ISSN = {1868-8969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17669},
URN = {urn:nbn:de:0030-drops-176690},
doi = {10.4230/LIPIcs.STACS.2023.17},
annote = {Keywords: reachability, cut arc, strong bridge, covering walk, safety, persistence, essentiality, genome assembly}
}
|
Keywords: |
|
reachability, cut arc, strong bridge, covering walk, safety, persistence, essentiality, genome assembly |
|
Collection: |
|
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
03.03.2023 |
