The Valve Location Problem in Simple Network Topologies

To control possible spills in liquid or gas transporting pipe systems, the systems are usually equipped with shutoff valves. In case of an accidental leak, these valves separate the system into a number of pieces, limiting the spill effect. In this paper, we consider the problem, for a given edge-weighted network representing a pipe system and for a given number of valves, of placing the valves in the network in such a way that the maximum possible spill, i.e., the maximum total weight of a piece, is minimized. We show that the problem is NP-hard even if restricted to any of the following settings: (i) series-parallel graphs, and hence graphs of treewidth two; and (ii) all edge weights equal one. If the network is a simple path, a cycle, or a tree, the problem can be solved in polynomial time. We also give a pseudopolynomial-time algorithm and a fully polynomial-time approximation scheme for networks of bounded treewidth.