
Finding a Shortest Nonzero Path in GroupLabeled Graphs via Permanent ComputationFinding a Shortest Nonzero Path in GroupLabeled Graphs via Permanent ComputationAA10679010 
"/Kobayashi, Yusuke/"Kobayashi, Yusuke ,
"/Toyooka, Sho/"Toyooka, Sho
77
(
4
)
, pp.1128

1142 , 201704 , Springer US
ISSN:01784617
NCID:AA10679010
Description
A grouplabeled graph is a directed graph with each arc labeled by a group element, and the label of a path is defined as the sum of the labels of the traversed arcs. In this paper, we propose a polynomial time randomized algorithm for the problem of finding a shortest st path with a nonzero label in a given grouplabeled graph (which we call the Shortest NonZero Path Problem). This problem generalizes the problem of finding a shortest path with an odd number of edges, which is known to be solvable in polynomial time by using matching algorithms. Our algorithm for the Shortest NonZero Path Problem is based on the ideas of Björklund and Husfeldt (Proceedings of the 41st international colloquium on automata, languages and programming, part I. LNCS 8572, pp 211–222, 2014). We reduce the problem to the computation of the permanent of a polynomial matrix modulo two. Furthermore, by devising an algorithm for computing the permanent of a polynomial matrix modulo 2r for any fixed integer r, we extend our result to the problem of packing internallydisjoint st paths.
FullText
https://tsukuba.repo.nii.ac.jp/?action=repository_action_common_download&item_id=41102&item_no=1&attribute_id=17&file_no=1