6

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

Craig Gidney
  • 1,518
  • 9
  • 21
  • 2
    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. – Yonatan N Jul 24 '20 at 02:53
  • 3
    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. https://arxiv.org/abs/1304.6740 – Chandra Chekuri Jul 24 '20 at 03:08
  • 1
    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? – D.W. Jul 24 '20 at 03:10
  • @D.W. https://i.stack.imgur.com/C3BNF.png shows a valid intermediate state of Bellman-Ford where it refuses to cross a crucial edge. – Craig Gidney Jul 24 '20 at 03:23
  • 1
    @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. – Yonatan N Jul 24 '20 at 04:43
  • @CraigGidney, thank you! Yonatan N, ahh, yes, that was what I missed - thank you! – D.W. Jul 24 '20 at 04:44
  • @Yonatan N: Bellman-Ford works perfectly also on undirected graphs (as long as we have no negative cycles, a trivial situation forcing this algorithm to go to $-\infty$). – Stasys Jul 25 '20 at 19:05
  • @CraigGidney There's a more fundamental problem with non-backtracking Bellman-Ford than what you outlined. In particular, the problem you demonstrated at the link could be solved by making a copy of each vertex for each possible neighboring vertex the path could have traveled from. However, there are non-simple negative cycles that don't involve immediate backtracking. For instance, suppose the path went A-B-C-D-E-B-A, where AB, BC,CD are -1 and DE, EB are+1. Non-backtracking Bellman-Ford would allow this, and fail. – isaacg Jul 26 '20 at 02:33
  • @isaacg Ah, right. I didn't state this, but I was assuming Bellman Ford always broke ties in favor of the existing predecessor. This prevents it from creating 0-weight cycles like BCDEB from your example. – Craig Gidney Jul 26 '20 at 05:36
  • @Stasys The naive implementation of Bellman-Ford on undirected graphs would fail as soon as the graph contains a single negative edge, as it would start hopping across it back and forth as if it is a cycle. While probably possible, patching B-F for undirected instances is inherently messy because the undirected shortest path problem with negative weights (and no negative cycles) does not have the nice structural property in which the shortest length-k walk from u to v would never traverse the same edge twice, so we can no longer treat shortest walks and shortest paths as identical concepts. – Yonatan N Jul 26 '20 at 09:27
  • @Yonatan N: thanks for clarification: for (naive) B&F, already edges whose repeated crossing decreases the weight are dangerous. – Stasys Jul 26 '20 at 16:55

0 Answers0