Welcome to MathOverflow

Question

1

I've posted a question on Stack Overflow regarding a seemingly NP-hard problem on maximization of weighted cycles in a graph problem.

One of the respondents cited Professor David Speyer's Math Overflow post in Math Overflow saying it's a polytime problem, while I argued it is not as I believe the solution of my problem can be used to solve a smaller travelling salesman problem. Unfortunately, that debate kind of ended here because the respondent stopped replying (he probably is busy and have forgotten about it or thought I am inexorably ignorant). Anyhow, I can't really rest until I know for certain it's an NP-hard problem or not. Can you guys help out?

Added by Brendan: The problem is, given an undirected graph with edge weights, find a set of vertex-disjoint cycles covering all the vertices and with maximum total weight.

edited May 24 at 1:24

Brendan McKay
9,111●1●13●33

asked May 23 at 23:32

Some Newbie
11●1

Brendan McKay · Answer 1 · 2012-05-24 01:23:02Z UTC

1

This problem is called "maximum cycle cover" and if you search with that phrase you'll find your answer. For example this paper says there is an $O(n^3)$ algorithm, but it cites it only to a PhD thesis. Maybe you can find a published proof.

For directed graphs, or undirected graphs where edges are treated as cycles of length 2 (so their weight counts twice), it is easy to do it in polynomial time using a maximum matching algorithm.

answered May 24 at 1:23

Brendan McKay
9,111●1●13●33

	Hmm, what's strange is that this paper here (arxiv.org/pdf/cs.cc/0504038.pdf) said:[br] 1. A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. (Yes, that applies) 2. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L. (Yes, that applies) [br] 3. Hell et al. showed that ﬁnding L-cycle covers in undirected graphs is NP-hard for almost all L [br][br] Unfortunately, I can't read Hell et al's paper or the paper you linked me to, since I am no longer in school. – Some Newbie May 24 at 3:48
	A specific example of my problem would be: [br] (1) There are 100 locations with edges being the distances between them (2) You want to draw 11 disjoint cycles with lengths x1,x2,...,x11 where x1+x2+...+x11 = 100 and the overall distances are maximized. In the simplest case of this type of problem with only 1 cycle of length 100 then thats the maximum Hamiltonian cycle problem (which should be NP-hard, my memory serves). – Some Newbie May 24 at 3:58
	Well, since there's no response, I suppose there's a problem with my reduction to Ham cycle? – Some Newbie May 30 at 2:02

Need input on a potentially NP-hard maximal edge-weighted multi-cycle graph

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.