Maximizing the Number of Spanning Trees in a Connected Graph

DOI10.1109/TIT.2019.2940263MaRDI QIDQ5211668zbMATH OpenOpenAlexFDO

Authors Stacy Patterson, Yuhao Yi, Zhongzhi Zhang, Hu-An Li

Publication date 28 January 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.02785

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40)

Abstract: We study the problem of maximizing the number of spanning trees in a connected graph by adding at most $k$ edges from a given candidate edge set. We give both algorithmic and hardness results for this problem: - We give a greedy algorithm that, using submodularity, obtains an approximation ratio of $(1-1/e-epsilon)$ in the exponent of the number of spanning trees for any $epsilon>0$ in time $ildeO(mepsilo{n}^{-1}+(n+q)epsilo{n}^{-3})$, where $m$ and $q$ is the number of edges in the original graph and the candidate edge set, respectively. Our running time is optimal with respect to the input size up to logarithmic factors, and substantially improves upon the $O(n^3)$ running time of the previous proposed greedy algorithm with approximation ratio $(1-1/e)$ in the exponent. Notably, the independence of our running time of $k$ is novel, comparing to conventional top-$k$ selections on graphs that usually run in $Omega(mk)$ time. A key ingredient of our greedy algorithm is a routine for maintaining effective resistances under edge additions in an online-offline hybrid setting. - We show the exponential inapproximability of this problem by proving that there exists a constant $c>0$ such that it is NP-hard to approximate the optimum number of spanning trees in the exponent within $(1-c)$. This inapproximability result follows from a reduction from the minimum path cover in undirected graphs, whose hardness again follows from the constant inapproximability of the Traveling Salesman Problem (TSP) with distances 1 and 2. Thus, the approximation ratio of our algorithm is also optimal up to a constant factor in the exponent. To our knowledge, this is the first hardness of approximation result for maximizing the number of spanning trees in a graph, or equivalently, by Kirchhoff's matrix-tree theorem, maximizing the determinant of an SDDM matrix.

Cited in

(13)

• Maximizing the number of spanning trees in \(K_n\)-complements of asteroidal graphs
• A new technique for the characterization of graphs with a maximum number of spanning trees
• The maximum \(f\)-depth spanning tree problem
• On numbers of vertices of maximum degree in the spanning trees of a graph
• scientific article; zbMATH DE number 4068900 (Why is no real title available?)
• Maximizing spanning trees in almost complete graphs
• Dynamic effective resistances and approximate Schur complement on separable graphs
• Maximizing convergence time in network averaging dynamics subject to edge removal
• Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition
• COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB
• Resistance distances in directed graphs: definitions, properties, and applications
• Maximizing the smallest eigenvalue of grounded Laplacian matrix
• On the non-submodularity of the problem of adding links to minimize the effective graph resistance

This page was built for publication: Maximizing the Number of Spanning Trees in a Connected Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211668)