Finding a cycle in a graph with the biggest value (the sum of all edges)

Question

I am trying to solve this problem: we have an oriented, weighted graph and we have to find a cycle with the biggest weight. Weight of a cycle is the sum of all edges forming the weight. The preferred solution is via backtracking.

My idea was to :

1. backtrack all combinations of vertexes (0s and 1s representing whether vertex is in a subgraph)
2. then verify if the subgraph is connected
3. then verify if a source vertex of any edge is in the subgraph is used only once
4. and then connecting the first vertex with the last one, thus forming a cycle.
5. If the sum of all weights is > then max, max = sum.

However, this solution doesn't work correctly on any almost any vertex. It finds a cycle, but it never finds the biggest one. Could you help me fix my algorithm? Thanks!

Answer 1

You should note that this problem is NP-hard (i.e., when all edges have uniform weight, a cycle of maximum weight is a Hamiltonian cycle). So unless your inputs are small or somehow usefully structured, it's probably a better idea to go for heuristics since there is likely no polynomial-time algorithm.

To fix your exact algorithm, possibly with a few tricks to speed things up as well, you can have a look at the description of an algorithm given by Rubin [1].

---

[1] Rubin, Frank. "A search procedure for Hamilton paths and circuits." Journal of the ACM (JACM) 21.4 (1974): 576-580.