Algorithmic aspects of graph-indexed random walks

01/16/2018

∙

by   Jan Bok, et al.

∙

0

∙

share

We study three problems regarding the so called graph-indexed random walks (or equivalently Lipschitz mappings of graphs). Computing the average range of graph-indexed random walk of a graph. Computing the maximum range of graph-indexed random walk for a given graph. Deciding if we can extend partial GI random walk into full GI random walk for a given graph. We show that while the first problem is #P-complete, the other two problems can be solved in polynomial time.