6
$\begingroup$

A simple path is a path that doesn't revisit a node. A simple cycle is a cycle that doesn't revisit an edge. You are given an undirected graph G which may contain edges of negative weight but which will not contain any simple cycles of negative weight. Is there an efficient algorithm for finding the minimum weight simple path between any two nodes of G?

Notes:

  1. Without the no-negative-simple-cycle constraint, this problem is NP-Hard.

  2. The reason I'm interested in this problem is because the weight of the min-weight simple path should be a good estimate of the "safety level" of the syndrome extracted during quantum error correction. In this case the edges of the graph correspond to physical error mechanisms, the negative edges are the physical errors that are part of the extracted syndrome, the no-negative-cycles property is guaranteed by the fact that the syndrome extraction would have used any such cycle to produce a better syndrome, and a simple path between two particular nodes can be multiplied into a syndrome to get a different syndrome that disagrees about the logical correction to make.

  3. I initially thought that the Bellman-Ford algorithm would work, after tweaking it so that each node refused to backtrack to its current predecessor. However, this can create deadlock situations where the optimal solution is to detour through multiple beneficial regions but the local greedy checks can't see past the initial cost of entering into a beneficial region. For example, in the graph below where you're trying to path from left to right, the optimal solution is to move vertically through almost all the negative edges (in red). Bellman-Ford can fail to find this solution, depending on the order in which the search progresses:

    deadlock example

$\endgroup$
11
  • 2
    $\begingroup$ There's a blog post here about the problem, but the equations seem to be broken. In any case, the author shows how to reduce the problem to a sequence of $O(n)$ min cost perfect matching calculations, and then expands on why that should not be optimal. $\endgroup$ – Yonatan N Jul 24 '20 at 2:53
  • 3
    $\begingroup$ This is a well-known problem that can be solved by reduction to min-cost perfect matching in general (non-bipartite) graphs. Not as well known as the case of directed graphs. You can find this reduction in books on combinatorial optimization. The paper corresponding to the blog post in the previous comment is this one I believe. arxiv.org/abs/1304.6740 $\endgroup$ – Chandra Chekuri Jul 24 '20 at 3:08
  • 1
    $\begingroup$ I'm a bit confused about in what way Bellman-Ford falls short? It finds the minimum-weight path (I believe that path will be simple as there are no negative cycles), so I'm struggling to see where it is not adequate? $\endgroup$ – D.W. Jul 24 '20 at 3:10
  • $\begingroup$ @D.W. i.stack.imgur.com/C3BNF.png shows a valid intermediate state of Bellman-Ford where it refuses to cross a crucial edge. $\endgroup$ – Craig Gidney Jul 24 '20 at 3:23
  • 1
    $\begingroup$ @D.W. Just in case you missed the quirk in the problem like like I did on the first read-through, Bellman-Ford is assumes that the input is a directed graph. The obvious undirected-to-directed reduction introduces negative length cycles. $\endgroup$ – Yonatan N Jul 24 '20 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.