A local search $4/3$-approximation algorithm for the minimum $3$-path partition problem

Yong Chen, Randy Goebel, Guohui Lin +5

Given a graph $G=(V,E)$, the $3$-path partition problem is to find a minimum collection of vertex-disjoint paths each of order at most $3$ to cover all the vertices of $V$. It i…