|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Safety in $s$-$t$ Paths, Trails and Walks | | Massimo Cairo
; Shahbaz Khan
; Romeo Rizzi
; Sebastian Schmidt
; Alexandru I. Tomescu
; | | Date: |
9 Jul 2020 | | Abstract: | Given a directed graph $G$ and a pair of nodes $s$ and $t$, an emph{$s$-$t$
bridge} of $G$ is an edge whose removal breaks all $s$-$t$ paths of $G$ (and
thus appears in all $s$-$t$ paths). Computing all $s$-$t$ bridges of $G$ is a
basic graph problem, solvable in linear time.
In this paper, we consider a natural generalisation of this problem, with the
notion of "safety" from bioinformatics. We say that a walk $W$ is emph{safe}
with respect to a set $mathcal{W}$ of $s$-$t$ walks, if $W$ is a subwalk of
all walks in $mathcal{W}$. We start by considering the maximal safe walks when
$mathcal{W}$ consists of: all $s$-$t$ paths, all $s$-$t$ trails, or all
$s$-$t$ walks of $G$. We show that the first two problems are immediate
linear-time generalisations of finding all $s$-$t$ bridges, while the third
problem is more involved. In particular, we show that there exists a compact
representation computable in linear time, that allows outputting all maximal
safe walks in time linear in their length.
We further generalise these problems, by assuming that safety is defined only
with respect to a subset of emph{visible} edges. Here we prove a dichotomy
between the $s$-$t$ paths and $s$-$t$ trails cases, and the $s$-$t$ walks case:
the former two are NP-hard, while the latter is solvable with the same
complexity as when all edges are visible. We also show that the same complexity
results hold for the analogous generalisations of emph{$s$-$t$ articulation
points} (nodes appearing in all $s$-$t$ paths).
We thus obtain the best possible results for natural "safety"-generalisations
of these two fundamental graph problems. Moreover, our algorithms are simple
and do not employ any complex data structures, making them ideal for use in
practice. | | Source: | arXiv, 2007.4726 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER