6

In a directed graph, we are looking for the cycle that had the lowest average edge weights. For instance, a graph with nodes 1 and 2 with path from 1 to 2 of length 2 and from 2 to 1 of length 4 would have minimum mean cycle of 3.

Not looking for a complicated method(Karp), but a simple backtracking wtih pruning solution. An explanation is given as "Solvable with backtracking with important pruning when current running mean is greater than the best found mean weight cycle cost."

However, why does this method work? If we are halfway through a cycle and the weight is more than the best found mean, isn't it possible that with small weight edges we can reach a situation where our current cycle can go lower than the best found mean?

Edit: Here is a sample problem: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2031

John Targaryen
  • 1,109
  • 1
  • 13
  • 29
  • @IrrationalPerson If someone needed to use STL libraries from c++ to explain, I could understand that. – John Targaryen Feb 17 '15 at 22:30
  • are you familiar with bfs / dfs ? – advocateofnone Feb 17 '15 at 23:02
  • Yes, familiar with BFS, DFS, Recursion, DP, Dijkstra. – John Targaryen Feb 17 '15 at 23:20
  • This question appears to be off-topic because it is not about programming or development. See [What topics can I ask about here](http://stackoverflow.com/help/on-topic) in the Help Center. Perhaps [Mathematics Stack Exchange](http://math.stackexchange.com/) or [Programmers Stack Exchange](http://programmers.stackexchange.com/) would be a better place to ask. – jww Feb 18 '15 at 03:10
  • @jww if graph theory is not programming then what is – John Targaryen Feb 18 '15 at 03:20
  • @Joe Bob - If you had a question about a concrete implementation, then it would be suitable for Stack Overflow. If you want to discuss theory about graphs, then there are more appropriate exchanges. I did not make the rules. – jww Feb 18 '15 at 03:27
  • I edited around the same time of your first comment to add a concrete problem, but I understand how you want a question about a specific implementation – John Targaryen Feb 18 '15 at 04:18

1 Answers1

2

Lets optimal solution for given graph be a cycle with avg edge weight X.

There is some optimal cycle with edges e_1, e_2 ... e_n, such that avg(e_i) = X.

For my proof, I assume all indexes modulo n, so e_(n + 1) is e_1.

Lets say that our heuristic can't find this solution, that means: for each i (whatever edge we took first) exists such j (we followed all edges from i to j so far) that average edge weight in the sequence e_i ... e_j is greater than X (heuristic prunes this solution).

Then we can show that average edge weight cannot be equal to X. Lets take a longest contiguos subsequence that is not pruned by heuristic (having average edge weight not greater than X for every element). At least one e_i <= X, so such subsequence exists. For the first element e_k of such subsequence, there is p such that avg(e_k ... e_p) > X. We take first such p. Now lets take k' = p + 1 and get another p'. We will repeat this process until we hit our initial k again. Final p may not outrun initial k, this mean that final subsequence contains initial [e_k, e_p - 1], which contradicts with our construction for e_k. Now our sequence e_1 ... e_n is completely covered by non-overlapping subsequences e_k ... e_p, e_k'...e_p' etc, each of those has average edge weight greater than X. So we have a contradiction that avg(e_i) = X.

As for your question:

If we are halfway through a cycle and the weight is more than the best found mean, isn't it possible that with small weight edges we can reach a situation where our current cycle can go lower than the best found mean?

Of course it is. But we can safely prune this solution, as later we will discover the same cycle starting from another edge, which will not be pruned. My proof states that if we consider every possible cycle in the graph, sooner or later we will find an optimal cycle.