Premium
Generalized loop‐erased random walks and approximate reachability
Author(s) -
Gorodezky Igor,
Pak Igor
Publication year - 2014
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20460
Subject(s) - reachability , mathematics , combinatorics , hypergraph , spanning tree , time complexity , discrete mathematics , reachability problem , random walk , random graph , directed graph , loop (graph theory) , polynomial , graph , statistics , mathematical analysis
Abstract In this paper we extend the loop‐erased random walk (LERW) to the directed hypergraph setting. We then generalize Wilson's algorithm for uniform sampling of spanning trees to directed hypergraphs. In several special cases, this algorithm perfectly samples spanning hypertrees in expected polynomial time. Our main application is to the reachability problem , also known as the directed all‐terminal network reliability problem. This classical problem is known to be # P ‐complete, hence is most likely intractable (Ball and Provan, SIAM J Comput 12 (1983) 777–788). We show that in the case of bi‐directed graphs , a conjectured polynomial bound for the expected running time of the generalized Wilson algorithm implies a FPRAS for approximating reachability. Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 201‐223, 2014