## Abstract

Given a graph G= (V, E) , we seek for a collection of vertex disjoint paths each of order at most 3 that together cover all the vertices of V. The problem is called 3-path partition, and it has close relationships to the well-known path cover problem and the set cover problem. The general k-path partition problem for a constant k≥ 3 is NP-hard, and it admits a trivial k-approximation. When k= 3 , the previous best approximation ratio is 1.5 due to Monnot and Toulouse (Oper Res Lett 35:677–684, 2007), based on two maximum matchings. In this paper we first show how to compute in polynomial time a 3-path partition with the least 1-paths, and then apply a greedy approach to merge three 2-paths into two 3-paths whenever possible. Through an amortized analysis, we prove that the proposed algorithm is a 13 / 9-approximation. We also show that the performance ratio 13 / 9 is tight for our algorithm.

Original language | English |
---|---|

Pages (from-to) | 150-164 |

Number of pages | 15 |

Journal | Journal of Combinatorial Optimization |

Volume | 38 |

Issue number | 1 |

DOIs | |

State | Published - Jul 15 2019 |

## Keywords

- Amortized analysis
- Approximation algorithm
- k-Path partition
- k-Set cover
- Path cover