On the Complexity of Finding a Minimum Cycle Cover of a Graph

1997/06/01 by Carsten Thomassen · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Interconnection Networks and Systems #graph theory and CDMA systems

paper · doi:10.1137/s0097539794267255

openalex publication_date 1997/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

We prove that the problem of finding a cycle cover of smallest total length is NP-hard. This confirms a conjecture of Itai, Lipton, Papadimitriou, and Rodeh from 1981. MSC codes 05C38 68Q25 Keywords complexity minimum cycle cover

Citations

• The NP-Completeness of Edge-Coloring

Cited by

• Arc routing [wikipedia]