ected graph, where V is the set of nodes and U is the set of edges. A k-path between nodes s, t ∈ V is a sequence of at most k edges connecting s and t. Given a non-negative weight function w: U → R + associated with the edges of G and a set D of pairs of origin-destination nodes, the 0-path network design problem (0PNDP) consists in finding a minimum weighted subset of edges U′ ⊆ U containing a 0-path between every origin-destination pair.  