On local search and placement of meters in networks

This work is motivated by the problem of placing pressure-meters in fluid networks. The problem is formally defined in graph-theoretic terms as follows. Given a graph, find a cotree (complement of a tree) incident upon the minimum number of vertices. We show that this problem is NP-hard and MAX SNP-hard. We design an algorithm with an approximation factor of 2+epsilon for this problem for any fixed epsilon>0. This approximation bound comes from the analysis of a local search heuristic, a common practical optimization technique that does not often allow formal worst-case analysis. The algorithm is made very efficient by finding restrictive definitions of the local neighborhoods to be searched. We also exhibit a polynomial time approximation scheme for this problem when the input is restricted to planar graphs.