An Approximation Algorithm for the Minimum Co‐Path Set Problem

We present an approximation algorithm for the problem of finding a minimum set of edges in a given graph G whose removal from G leaves a graph in which each connected component is a path. It achieves a ratio of $\frac{10}{7}$ and runs in O(n ^1.5) time, where n is the number of vertices in the input graph. The previously best approximation algorithm for this problem achieves a ratio of 2 and runs in O(n ²) time.