On Valve Adjustments that Interrupt all s-t-Paths in a Digraph

TitleOn Valve Adjustments that Interrupt all s-t-Paths in a Digraph
Publication TypeTechnical Report
Year of Publication1993
AuthorsHuckenbeck, U.
Other Numbers869

(Pages: 15) When searching a path in a digraph, usually the following situation is given: Every node v may be entered by an arbitrary incoming arc (u,v), and v may be left by an arbitrary outgoing arc (v,w).In this paper, however, we consider graphs with valve nodes, which 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.

Bibliographic Notes

ICSI Technical Report TR-93-081

Abbreviated Authors

U. Huckenbeck

ICSI Publication Type

Technical Report