Approximating the maximum weight cycle/path partition in graphs with weights one and two

Xinmeng Guo (), Wei Yu () and Zhaohui Liu ()
Additional contact information
Xinmeng Guo: East China University of Science and Technology
Wei Yu: East China University of Science and Technology
Zhaohui Liu: East China University of Science and Technology

Journal of Combinatorial Optimization, 2025, vol. 49, issue 5, No 14, 26 pages

Abstract: Abstract In this paper, we investigate the maximum weight k-cycle (k-path) partition problem (MaxWkCP/MaxWkPP for short). The input consists of an undirected complete graph $$G=(V,E)$$ G = ( V , E ) with $$|V|=kn$$ | V | = k n , where k, n are positive integers, and a non-negative weight function on E, the objective is to determine n vertex disjoint k-cycles (k-paths), which are cycles (paths) containing exactly k vertices, covering all the vertices such that the total edge weight of these cycles (paths) is as large as possible. We propose improved approximation algorithms for the MaxWkCP/MaxWkPP in graphs with weights one and two. For the MaxWkCP in graphs with weights one and two, we obtain an approximation algorithm having an approximation ratio of $$\frac{37}{48}$$ 37 48 for $$k=6$$ k = 6 , which improves upon the best available $$\frac{91}{120}$$ 91 120 -approximation algorithm by Zhao and Xiao 2024a. When $$k=4$$ k = 4 , we show that the same algorithm is a $$\frac{7}{8}$$ 7 8 -approximation algorithm and give a tight example. This ratio ties with the state-of-the-art result, also given by Zhao and Xiao 2024a. However, we demonstrate that our algorithm can be applied to the minimization variant of MaxWkCP in graphs with weights one and two and achieve a tight approximation ratio of $$\frac{5}{4}$$ 5 4 . For the MaxW5PP in graphs with weights one and two, we devise a novel $$\frac{19}{24}$$ 19 24 -approximation algorithm by combining two separate algorithms, each of which handles one of the two complementary scenarios of the optimal solution well. This ratio is better than the previous best ratio of $$\frac{3}{4}$$ 3 4 due to Li and Yu 2023.

Keywords: Approximation Algorithm; Cycle Partition; Path Partition; Matching (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01322-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:5:d:10.1007_s10878-025-01322-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01322-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().