Cycle of maximum weight in a graph

Question

Given a weighted graph (directed or undirected) I need to find the cycle of the graph with the maximum weight.

The weight of a cycle being the sum of the weight of the edges of the graph.

It can be any cycle, not just base cycle for which we can

• find all base cycle (see http://stackoverflow.com/questions/1607124/algorithms-to-identify-all-the-cycle-bases-in-a-undirected-graph )
• compute the weight of each base cycle and find the maximum

I could try to enumerate all cycles of the graph and then compute the maximum but the total number of cycles can be really big (if the graph is complete then any sequence of vertices where the first and last one are identical is a cycle).

Do you have any idea to find that maximum weight cycle without enumerating all cycles ?

If you need hypothesis on the graph (positives weights for example) please indicates them.

Answer 1

This is NP-Complete.

Hamiltonian Cycle problem can be reduced to this.

Given a graph for which we need to check if there exists a Hamiltonian Cycle or not, assign weight 1 to each edge.

Now run your algorithm to get the maximum weight cycle. If the weight is < n, then the original graph has no Hamiltonian cycle, otherwise it does.

Answer 2

If you can find the minimum weighted path in your specific case, just reverse the signs of all the weights and apply your algorithm. Of course you are making some unstated assumptions because Moron's argument is correct (no pun intended). The assumptions you are making could be positive weights or no negative weight cycles. I think you should make an effort to state them instead of letting people search in the infinite space of possible assumptions. As to hardness results, this is also hard to approximate in a number of way, check out this paper. The same paper contains several positive results for important types of graphs, but it's concerned with longest unweighted paths so my guess is that most algorithms in the paper won't directly help in your case. If you search for "Heavy cycles" you will find a number of interesting papers, but they are more mathematical in character. If your weights are small integers (up to a polynomial in the size of the graph), you can try and replace every edge with an unweighted path to reduce your problem to the unweighted case. I hope this helps to some degree, but you might have an open research problem on your hands.