On Valve Adjustments that Interrupt all s-t-Paths in a Digraph
Citations Over Time
Abstract
When searching for a path in a digraph, usually the following situation is given: Each node $v$ may be entered via an arbitrary incoming arc $(u,v)$, and $v$ may be left via an arbitrary outgoing arc $(v, w)$. This paper, however, is addressed to graphs with valve nodes, and these nodes cannot arbitrarily be entered and left. More precisely, a movable valve is installed in each valve node $v$. Entering $v$ via $(u,v)$ and leaving it via $(v, w)$ is only possible if the current position of the valve generates a connection between these two arcs; if, however, the current valve adjustment interrupts this connection then every path using the arcs $(u,v)$ and $(v,w)$ is interrupted, too. We investigate the complexity of the following problem: Given a digraph with valve nodes. Let $s$ and $t$ be two nodes of this graph. Does there exist a valve adjustment that interrupts all paths from $s$ to $t$? We show that this problem can be solved in deterministic polynomial time if all valve nodes belong to a particular class of valves; otherwise, the problem is NP-complete.
Related Papers
- → Complexity Issues in Switching of Graphs(2000)18 cited
- → Graph-Theoretic Concepts in Computer Science(1992)2 cited
- Computing the Expected Maximum Number of Vertex-Disjoint s-t Paths in a Probabilistic Basically Series-Parallel Digraph(1993)
- → On valve adjustments that interrupt all s-t-paths in a digraph(1997)1 cited
- → Node-to-set disjoint paths in substring reversal graphs(2011)