Generalized loop‐erased random walks and approximate reachability. Issue 2 (6th December 2012)

• Record Type: Journal Article
• Authors: Gorodezky, Igor; Pak, Igor
• Is Part Of: Random structures & algorithms. Volume 44:Issue 2(2014)
• Page Start: 201
• Page End: 223
• Publication Date: 2012-12-06
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20460
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>In this paper we extend the <italic>loop‐erased random walk</italic> (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 <italic>reachability problem</italic>, also known as the directed all‐terminal network reliability problem. This classical problem is known to be # <italic>P</italic>‐complete, hence is most likely intractable (Ball and Provan, SIAM J Comput 12 (1983) 777–788). We show that in the case of <italic>bi‐directed graphs</italic>, 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</p> </abstract>