For a weighted graph, the Minimum-Weight Cycle Cover Problem (MWCCP) is the problem to find a cycle cover with minimal sum of weights of edges in all cycles of the cover.
For bridgeless planar graphs, the MWCCP can be solved in polynomial time.
It has been proven that every bridgeless graph has cycle k-cover for any even integer k≥4.
For k=2, it is the well-known cycle double cover conjecture is an open problem in graph theory.
The cycle double cover conjecture states that in every bridgeless graph, there exists a set of cycles that together cover every edge of the graph twice.