×

Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth. (English) Zbl 1438.05044

Summary: 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, \dots , n\). The running time of our algorithm is \(O((B(p+1))^3pn^3)\), where \(B(p+1)\) is the \((p+1)\)-th Bell number.

MSC:

05C05 Trees
05C30 Enumeration in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Benjamini, I., Lyons, R., Peres, Y., Schramm, O.: Uniform spanning forests. Ann. Probab. 29, 1-65 (2001) · Zbl 1016.60009
[2] Brown, T.J., Mallion, R.B., Pollak, P., Roth, A.: Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes. Discrete Appl. Math. 67, 51-66 (1996) · Zbl 0846.05087
[3] Caracciolo, S., Jacobsen, J.L., Saleur, H., Sokal, A.D., Sportiello, A.: Fermionic field theory for trees and forests. Phys. Rev. Lett. 93, 080601 (2004)
[4] Deng, Y., Garoni, T.M., Sokal, A.D.: Ferromagnetic phase transition for the spanning-forest model \[(q\rightarrow 0\] q→0 limit of the Potts model) in three or more dimensions. Phys. Rev. Lett. 98, 030602 (2007)
[5] Liu, C.J., Chow, Y.: Enumeration of forests in a graph. Proc. Am. Math. Soc. 83, 659-662 (1981) · Zbl 0477.05039
[6] Stark, D.: The asymptotic number of spanning forests of complete bipartite labelled graphs. Discrete Math. 313, 1256-1261 (2013) · Zbl 1277.05150
[7] Myrvold, W.: Counting \[k\] k-component forests of a graph. Networks 22, 647-652 (1992) · Zbl 0773.90084
[8] Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Computing the Tutte polynomial in vertex-exponential time. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 677-686. IEEE. New York (2008)
[9] Teranishi, Y.: The number of spanning forests of a graph. Discrete Math. 290, 259-267 (2005) · Zbl 1058.05040
[10] Jaeger, F., Vertigan, D., Welsh, D.: On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Camb. Philos. Soc. 108, 35-53 (1990) · Zbl 0747.57006
[11] Vertigan, D.L., Welsh, D.J.A.: The computational complexity of the Tutte plane: the bipartite case. Combin. Probab. Comput. 1, 181-187 (1992) · Zbl 0793.05091
[12] Gebauer, H., Okamoto, Y.: Fast exponential-time algorithms for the forest counting and the Tutte polynomial computation in graph classes. Int. J. Found. Comput. Sci. 20, 25-44 (2009) · Zbl 1160.05033
[13] Kirchhoff, G.: Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. Ann. Phys. Chem. 72, 497-508 (1847)
[14] Palmer, E.M.: On the spanning tree packing number of a graph: a survey. Discrete Math. 230, 13-21 (2001) · Zbl 0980.05020
[15] Comellas, F., Miralles, A., Liu, H., Zhang, Z.: The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs. Phys. A 392, 2803-2806 (2013) · Zbl 1395.05157
[16] Bogdanowicz, Z.R.: Formulas for the number of spanning trees in a fan. Appl. Math. Sci. 2, 781-786 (2008) · Zbl 1166.05015
[17] Xiao, Y., Zhao, H.: New method for counting the number of spanning trees in a two-tree network. Phys. A 392, 4576-4583 (2013) · Zbl 1395.05174
[18] Zhang, Z., Wu, B., Comellas, F.: The number of spanning trees in Apollonian networks. Discrete Appl. Math. 169, 206-213 (2014) · Zbl 1288.05066
[19] Stones, R.J.: Computing the number of \[h\] h-edge spanning forests in complete bipartite graphs. Discrete Math. Theor. Comput. Sci. 16, 313-326 (2014) · Zbl 1294.05053
[20] Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 309-322 (1986) · Zbl 0611.05017
[21] Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85, 12-75 (1990) · Zbl 0722.03008
[22] Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12, 308-340 (1991) · Zbl 0734.68073
[23] Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7, 555-581 (1992) · Zbl 0753.05062
[24] Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86-111 (2015) · Zbl 1327.68126
[25] Berend, D., Tassa, T.: Improved bounds on Bell numbers and on moments of sums of random variables. Probab. Math. Stat. 30, 185-205 (2010) · Zbl 1230.60014
[26] Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305-1317 (1996) · Zbl 0864.68074
[27] Bodlaender, H.L., Koster, A.M.: Treewidth computations I. Upper bounds. Inf. Comput. 208, 259-275 (2010) · Zbl 1186.68328
[28] Bodlaender, H.L.: A partial \[k\] k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1-45 (1998) · Zbl 0912.68148
[29] Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, London (2008) · Zbl 1134.05001
[30] Kloks, T.: Treewidth: Computations and Approximations. Lecture Notes in Computer Science, vol. 842. Springer, Berlin (1994) · Zbl 0825.68144
[31] Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Proceedings of Foundations of Computer Science, pp. 150-159. IEEE (2011) · Zbl 1292.68122
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.