Computing Cycle Covers without Short Cycles

摘要: A cycle cover of a graph is spanning subgraph where each node part exactly one simple cycle. k-cycle has length at least k. We call the decision problems whether directed or undirected k-DCC and k-UCC. Given with edge weights two, Min-k-DCC Min-k-UCC are minimization finding minimum weight. We present factor 4=3 approximation algorithms for running time O(n5/2) (independent k). Specifically, we obtain 4/3 algorithm asymmetric travelling salesperson problem distances two 2/3 path packing same time. On other hand, show that NP-complete k ≥ 3 no PTAS 4, unless P = NP. Furthermore, design polynomial 7/6 Min-k-UCC. As lower bound, prove 12, NP.