Paper Info
Title
On the Stable Paths Problem
Abstract
The Border Gateway Protocol (BGP) is the interdomain routing protocol used to exchange routing information between Autonomous Systems (ASes) in the internet today. While intradomain routing protocols such as RIP are basically distributed algorithms for solving shortest path problems, the graph theoretic problem that BGP is trying to solve is the stable paths problem (SPP). Unfortunately, unlike shortest path problems, it has been shown that instances of SPP can fail to have a solution, and so BGP can fail to converge. We define a fractional version of SPP and show that all instances of fractional SPP have solutions. We also show that there are polynomial time reductions from a number of well-known graph problems to SPP. For example, finding stable matchings in hypergraphic preference systems (a generalization of graph stable matchings to the case of hypergraphs) and computing kernels in directed graphs are both polynomial time reducible to SPP. These reductions remain valid in the fractional case. Thus the existence of a polynomial time algorithm for computing fractional solutions to SPP would imply polynomial time algorithms for fractional solutions to these other problems as well.
Year
DOI
Venue
2010
10.1137/080730019
SIAM J. Discrete Math.
Keywords
Field
DocType
fractional spp,shortest path problem,polynomial time reduction,fractional solution,stable paths problem,fractional case,graph theoretic problem,fractional version,polynomial time algorithm,polynomial time reducible,graph stable matchings,border gateway protocol,stable matching,polynomial time,distributed algorithm,directed graph,routing protocol
Discrete mathematics,Combinatorics,Shortest path problem,Constraint graph,Hypergraph,Directed graph,Matching (graph theory),Border Gateway Protocol,Time complexity,Mathematics,Routing protocol
Journal
Volume
Issue
ISSN
24
3
0895-4801
Citations 
PageRank 
References 
2
0.38
6
Authors
2
Name
Order
Citations
PageRank
P. E. Haxell121226.40
G. T. Wilfong2131.21