## Abstract

The minimum k-path partition (Min-k-PP for short) problem targets to partition an input graph into the smallest number of paths, each of which has order at most k. We focus on the special case when k = 3. Existing literature mainly concentrates on the exact algorithms for special graphs, such as trees. Because of the challenge of NP-hardness on general graphs, the approximability of the Min-3-PP problem attracts researchers' attention. The first approximation algorithm dates back about 10 years and achieves an approximation ratio of ^{3}_{2} , which was recently improved to ^{13}_{9} and further to ^{4}_{3} . We investigate the ^{3}_{2} -approximation algorithm for the Min-3-PP problem and discover several interesting structural properties. Instead of studying the unweighted Min-3-PP problem directly, we design a novel weight schema for `-paths, ` ∈ {1, 2, 3}, and investigate the weighted version. A greedy local search algorithm is proposed to generate a heavy path partition. We show the achieved path partition has the least 1-paths, which is also the key ingredient for the algorithms with ratios ^{13}_{9} and ^{4}_{3} . When switching back to the unweighted objective function, we prove the approximation ratio ^{21}_{16} via amortized analysis.

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

Title of host publication | 30th International Symposium on Algorithms and Computation, ISAAC 2019 |

Editors | Pinyan Lu, Guochuan Zhang |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959771306 |

DOIs | |

State | Published - Dec 2019 |

Event | 30th International Symposium on Algorithms and Computation, ISAAC 2019 - Shanghai, China Duration: Dec 8 2019 → Dec 11 2019 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 149 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 30th International Symposium on Algorithms and Computation, ISAAC 2019 |
---|---|

Country/Territory | China |

City | Shanghai |

Period | 12/8/19 → 12/11/19 |

## Keywords

- 3-path partition
- Amortized analysis
- Approximation algorithm
- Exact set cover
- Local search

## Fingerprint

Dive into the research topics of 'A^{21}

_{16}-approximation for the minimum 3-path partition problem'. Together they form a unique fingerprint.