Computing the Number of k -Component Spanning Forests of a Graph with Bounded Treewidth
- PDF / 283,573 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 227 Views
Computing the Number of k-Component Spanning Forests of a Graph with Bounded Treewidth Peng-Fei Wan1,2 · Xin-Zhuang Chen1 Received: 28 May 2018 / Revised: 24 October 2018 / Accepted: 9 February 2019 / Published online: 5 March 2019 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract Let G be a graph on n vertices with bounded treewidth. We use f k (G) to denote the number of spanning forests of G with k components. Given a tree decomposition of width at most p of G, we present an algorithm to compute f k (G) for k = 1, 2, · · · , n. The running time of our algorithm is O((B( p + 1))3 pn 3 ), where B( p + 1) is the ( p + 1)-th Bell number. Keywords Spanning tree · Spanning forest · Bounded treewidth · Dynamic programming Mathematics Subject Classification 05C05 · 05C30 · 05C85
1 Introduction In this paper, we consider only simple, undirected and finite graphs. A graph having no cycles is a forest, and a connected forest is a tree. Let G be a graph. A spanning forest of G is a forest whose vertex set is the entire vertex set of G. We use f k (G) to denote the number of spanning forests of G with k components. Both of the total number of spanning forests and the number of k-component spanning forests are important graph
This research was supported by the National Natural Science Foundation of China (Nos. 11571135, 11671320 and 11601430).
B
Peng-Fei Wan [email protected] Xin-Zhuang Chen [email protected]
1
Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi’an 710029, China
2
School of Mathematics and Statistics, Yulin University, Yulin 719000, Shaanxi, China
123
386
P.-F. Wan, X.-Z. Chen
invariants [1] with lots of applications in many disciplines [2–4]. Many efforts have been devoted to calculating the values of these parameters [5–9]. It is #P-complete to compute the total number of forests in a graph [10], even in a bipartite planar graph [11]. By using Kirchhoff’s matrix tree theorem and the inclusion–exclusion principle, Björklund et al. [8] proposed an algorithm that could compute the total number of spanning forests of an n-vertex graph in time 2n n O(1) . Gebauer and Okamoto [12] proposed algorithms to compute the number of forests for interval graphs and 3-regular graphs with running time O(1.970 6m ) and O(1.849 4m ), respectively. Many efforts have also been devoted to computing the number of k-component spanning forests of a graph for a fixed k. Specially, a spanning forest of a graph G with one component is a spanning tree of G. Denote by τ (G) the number of spanning trees of G, i.e., τ (G) = f 1 (G). A famous and classical result on τ (G) is the Kirchhoff’s matrix tree theorem [13] which states that all cofactors of L are equal to τ (G), where L is the Laplacian matrix of G. It is also possible to give explicit and simple formulas for the number of spanning trees [14,15] for some special classes of graphs, such as fan
Data Loading...
