Algorithmic aspects of graph-indexed random walks.
Jan Bok · arXiv (Cornell University) · 2018
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.