More Like this

1. 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
2. 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
3. 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
4. An Exact‐Arithmetic Algorithm for Spanning Tree Modulus

   https://doi.org/10.1002/net.22270  

   Albin, Nathan; Kottegoda, Kapila; Poggi‐Corradini, Pietro (February 2025, Networks)

   ABSTRACT Spanning tree modulus is a generalization of effective resistance that is closely related to graph strength and fractional arboricity. The optimal edge density associated with the spanning tree modulus is known to produce two hierarchical decompositions of arbitrary graphs, one based on strength and the other on arboricity. Here we introduce an exact‐arithmetic algorithm for spanning tree modulus and the strength‐based decomposition using Cunningham's algorithm for graph vulnerability. The algorithm exploits an interesting connection between the spanning tree modulus and critical edge sets from the vulnerability problem. This paper introduces the new algorithm, describes a practical means for implementing it using integer arithmetic, and presents some examples and computational time scaling tests. 

   more » « less
5. Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree

   https://doi.org/10.1002/jgt.22880  

   Scott, Alex; Seymour, Paul; Spirkl, Sophie (September 2022, Journal of Graph Theory)

   Abstract Let be a tree. It was proved by Rödl that graphs that do not contain as an induced subgraph, and do not contain the complete bipartite graph as a subgraph, have bounded chromatic number. Kierstead and Penrice strengthened this, showing that such graphs have bounded degeneracy. Here we give a further strengthening, proving that for every tree , the degeneracy is at most polynomial in . This answers a question of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak. 

   more » « less