Local improvement algorithms for a path packing problem: A performance analysis based on linear programming

Abstract Given a graph, we wish to find a maximum number of vertex-disjoint paths of length 2. We propose a series of local improvement algorithms for this problem, and present a linear-programming based method for analyzing their performance.