2026-07-21T14:17:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7563 2024-03-06T10:40:37Z ddc:004 open_access

Density Independent Algorithms for Sparsifying k-Step Random Walks Jindal, Gorav Kolev, Pavel Peng, Richard Sawlani, Saurabh random walks graph sparsification spectral graph theory effective resistances We give faster algorithms for producing sparse approximations of the transition matrices of k-step random walks on undirected and weighted graphs. These transition matrices also form graphs, and arise as intermediate objects in a variety of graph algorithms. Our improvements are based on a better understanding of processes that sample such walks, as well as tighter bounds on key weights underlying these sampling processes. On a graph with n vertices and m edges, our algorithm produces a graph with about nlog(n) edges that approximates the k-step random walk graph in about m + k^2 nlog^4(n) time. In order to obtain this runtime bound, we also revisit "density independent" algorithms for sparsifying graphs whose runtime overhead is expressed only in terms of the number of vertices. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gorav Jindal and Pavel Kolev and Richard Peng and Saurabh Sawlani 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.14 urn:nbn:de:0030-drops-75638 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.14 eng https://creativecommons.org/licenses/by/3.0/legalcode