|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc020102,
author = {Ulrich Huckenbeck},
title = {On Valve Adjustments that Interrupt
all $s$-$t$-Paths in a Digraph},
journal = jalc,
year = 1997,
volume = 2,
number = 1,
pages = {19--45},
keywords = {graph theory, paths in graphs, complexity theory,
NP-completeness},
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)$.\par
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:
\begin{quote}
Given a digraph with valve nodes.
Let $s$ and $t$ be two nodes of this graph.\newline
Does there exist a valve adjustment that interrupts
all paths from $s$ to $t$?
\end{quote}
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.}
}