The 2‐path network problem

Abstract

Abstract Given a graph with nonnegative edge weights and a set D of node pairs, the 2‐ path network problem requires a minimum weight set of edges such that the induced subgraph contains a path with one or two edges connecting each pair in D . The problem is NP ‐hard. We present two integer programming models for the problem and study properties of associated polytopes, including cutting planes. Two approximation algorithms are suggested and analyzed. Some computational experience is reported. © 2004 Wiley Periodicals, Inc.