Two edge-disjoint HOP-constrained paths and polyhedra

Given a graph G with distinguished nodes s and t, a cost on each edge of G, and a fixed integer L ≥ 2, the two edge-disjoint hop-constrained paths problem is to find a minimum cost subgraph such that between s and t there exist at least two edge-disjoint paths of length at most L. In this paper, we consider that problem from a polyhedral point of view. We give an integer programming formulation for the problem when L = 2, 3. An extension of this result to the more general case where the number of required paths is arbitrary and L = 2, 3 is also given. We discuss the associated polytope, P(G, L), for L = 2, 3. In particular, we show in this case that the linear relaxation of P(G, L), Q(G, L), given by the trivial, the st-cut, and the so-called L-path-cut inequalities, is integral. As a consequence, we obtain a polynomial time cutting plane algorithm for the problem when L = 2, 3. We also give necessary and sufficient conditions for these inequalities to define facets of P(G, L) for L ≥ 2 when G is complete. We finally investigate the dominant of P(G, L) and give a complete description of this polyhedron for L ≥ 2 when P(G, L) = Q(G, L). © 2004 Society for Industrial and Applied Mathematics.SCOPUS: ar.j