The valve location problem in simple network topologies

Hans L. Bodlaender, Alexander Grigoriev, Nadejda V. Grigorieva, Albert Hendriks

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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, to place 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) for series-parallel graphs and hence for graphs of treewidth two; (ii) if 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 pseudo-polynomial time algorithm and a fully polynomial approximation scheme for networks of bounded treewidth.

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 34th International Workshop, WG 2008, Revised Papers
Number of pages11
Publication statusPublished - 2008
Event34th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2008 - Durham, United Kingdom
Duration: 30 Jun 20082 Jul 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5344 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference34th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2008
Country/TerritoryUnited Kingdom


  • Binary search
  • Bounded treewidth
  • Computational complexity
  • Dynamic programming
  • Valve location problem


Dive into the research topics of 'The valve location problem in simple network topologies'. Together they form a unique fingerprint.

Cite this