Finding k Shortest Paths in Cayley Graphs of Finite Groups

Abstract We present a new method for finding k shortest paths between any two vertices in the Cayley graph $$\text {Cay}(G, S)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>Cay</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>,</mml:mo> <mml:mi>S</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> of a finite group G with its generating set S closed under inverses. By using a reduced convergent rewriting system R for G , we first find the lexicographically minimal shortest path between two vertices in $$\text {Cay}(G, S)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>Cay</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>,</mml:mo> <mml:mi>S</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Then, by symmetrizing the length-preserving rules of R , we provide a polynomial time algorithm (in the size of certain rewrite rules, the lexicographically minimal shortest path, and k ) for finding k shortest paths between two vertices in $$\text {Cay}(G, S)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>Cay</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>,</mml:mo> <mml:mi>S</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Our implementation of finding k shortest paths between two vertices in $$\text {Cay}(G, S)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>Cay</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>,</mml:mo> <mml:mi>S</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is also discussed.