Iterative Message Passing Algorithm for Vertex-Disjoint Shortest Paths

As an algorithmic framework, message passing is extremely powerful and has wide applications in the context of different disciplines including communications, coding theory, statistics, signal processing, artificial intelligence and combinatorial optimization. In this paper, we investigate the performance of a message-passing algorithm called min-sum belief propagation (BP) for the vertex-disjoint shortest k-path problem (k-VDSP) on weighted directed graphs, and derive the iterative message-passing update rules. As the main result of this paper, we prove that for a weighted directed graph G of order n, BP algorithm converges to the unique optimal solution of k -VDSP on G within O(n(2) w(max)) iterations, provided that the weight we is nonnegative integral for each arc e is an element of E(G), where w(max) = max{w(e) : e is an element of E(G)}. To the best of our knowledge, this is the first instance where BP algorithm is proved correct for NP-hard problems. Additionally, we establish the extensions of k-VDSP to the case of multiple sources or sinks.

Automated summary

This paper investigates the performance of the min-sum belief propagation (BP) algorithm for the vertex-disjoint shortest k-path problem (k-VDSP) on weighted directed graphs. The paper derives iterative message-passing update rules and proves that the BP algorithm converges to the unique optimal solution in a certain number of iterations. This is the first instance where the BP algorithm is proven to be correct for NP-hard problems.