More Like this

1. On the typical structure of graphs not containing a fixed vertex‐critical subgraph

   https://doi.org/10.1002/rsa.21228  

   Engelberg, Oren; Samotij, Wojciech; Warnke, Lutz (December 2024, Random Structures & Algorithms)

   Abstract This work studies the typical structure of sparse ‐free graphs, that is, graphs that do not contain a subgraph isomorphic to a given graph . Extending the seminal result of Osthus, Prömel, and Taraz that addressed the case where is an odd cycle, Balogh, Morris, Samotij, and Warnke proved that, for every , the structure of a random ‐free graph with vertices and edges undergoes a phase transition when crosses an explicit (sharp) threshold function . They conjectured that a similar threshold phenomenon occurs when is replaced by any strictly 2‐balanced, edge‐critical graph . In this paper, we resolve this conjecture. In fact, we prove that the structure of a typical ‐free graph undergoes an analogous phase transition for every in a family of vertex‐critical graphs that includes all edge‐critical graphs. 

   more » « less
2. Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees

   https://doi.org/10.1109/FOCS.2017.90  

   Durfee, David; Peebles, John; Peng, Richard; Rao, Anup B. (November 2017, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017)

   We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs, which by Kirchhoff's matrix-tree theorem, is equivalent to determinant of a graph Laplacian minor, or equivalently, of any SDDM matrix. Our analyses utilizes this combinatorial connection to bridge between statistical leverage scores / effective resistances and the analysis of random graphs by [Janson, Combinatorics, Probability and Computing `94]. This leads to a routine that in quadratic time, sparsifies a graph down to about $$n^{1.5}$$ edges in ways that preserve both the determinant and the distribution of spanning trees (provided the sparsified graph is viewed as a random object). Extending this algorithm to work with Schur complements and approximate Choleksy factorizations leads to algorithms for counting and sampling spanning trees which are nearly optimal for dense graphs. We give an algorithm that computes a $$(1 \pm \delta)$$ approximation to the determinant of any SDDM matrix with constant probability in about $$n^2 \delta^{-2}$$ time. This is the first routine for graphs that outperforms general-purpose routines for computing determinants of arbitrary matrices. We also give an algorithm that generates in about $$n^2 \delta^{-2}$$ time a spanning tree of a weighted undirected graph from a distribution with total variation distance of $$\delta$$ from the $$w$$-uniform distribution . 

   more » « less
3. The diameter of the uniform spanning tree of dense graphs

   https://doi.org/10.1017/S0963548322000062  

   Alon, Noga; Nachmias, Asaf; Shalev, Matan (November 2022, Combinatorics, Probability and Computing)

   Abstract We show that the diameter of a uniformly drawn spanning tree of a simple connected graph on n vertices with minimal degree linear in n is typically of order $$\sqrt{n}$$ . A byproduct of our proof, which is of independent interest, is that on such graphs the Cheeger constant and the spectral gap are comparable. 

   more » « less
4. Exact sampling of spanning trees via fast-forwarded random walks

   https://doi.org/10.1093/biomet/asaf031  

   Tam, Edric; Dunson, David B; Duan, Leo L (January 2025, Biometrika)

   Summary Tree graphs are used routinely in statistics. When estimating a Bayesian model with a tree component, sampling the posterior remains a core difficulty. Existing Markov chain Monte Carlo methods tend to rely on local moves, often leading to poor mixing. A promising approach is to instead directly sample spanning trees on an auxiliary graph. Current spanning tree samplers, such as the celebrated Aldous–Broder algorithm, rely predominantly on simulating random walks that are required to visit all the nodes of the graph. Such algorithms are prone to getting stuck in certain subgraphs. We formalize this phenomenon using the bottlenecks in the random walk’s transition probability matrix. We then propose a novel fast-forwarded cover algorithm that can break free from bottlenecks. The core idea is a marginalization argument that leads to a closed-form expression that allows for fast-forwarding to the event of visiting a new node. Unlike many existing approximation algorithms, our algorithm yields exact samples. We demonstrate the enhanced efficiency of the fast-forwarded cover algorithm, and illustrate its application in fitting a Bayesian dendrogram model on a Massachusetts crime and community dataset. 

   more » « less
5. On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs

   Cohen-Addad, Vincent; Filtser, Arnold; Klein, Philip N; Le, Hung (October 2020, Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science)

   null (Ed.)

   Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a “small-complexity” graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minor-free metrics: 1) Construction of a light subset spanner. Given a subset of vertices called terminals, and ϵ, in polynomial time we construct a sub graph that preserves all pairwise distances between terminals up to a multiplicative 1+ϵ factor, of total weight at most Oϵ(1) times the weight of the minimal Steiner tree spanning the terminals. 2) Construction of a stochastic metric embedding into low treewidth graphs with expected additive distortion ϵD. Namely, given a minor-free graph G=(V,E,w) of diameter D, and parameter ϵ, we construct a distribution D over dominating metric embeddings into treewidth-Oϵ(log n) graphs such that ∀u,v∈V, Ef∼D[dH(f(u),f(v))]≤dG(u,v)+ϵD. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minor-free metrics; (2) the first approximation scheme for bounded-capacity vehicle routing in minor-free metrics; (3) the first efficient approximation scheme for bounded-capacity vehicle routing on bounded genus metrics. En route to the latter result, we design the first FPT approximation scheme for bounded-capacity vehicle routing on bounded-treewidth graphs (parameterized by the treewidth). 

   more » « less