The 2-path network problem

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.