Dourado, Mitre C.; Oliveira, Rodolfo A.; Protti, Fábio Algorithmic aspects of Steiner convexity and enumeration of Steiner trees. (English) Zbl 1332.90326 Ann. Oper. Res. 223, 155-171 (2014). Summary: For a set \(W\) of vertices of a connected graph \(G=(V(G),E(G))\), a Steiner \(W\)-tree is a connected subgraph \(T\) of \(G\) such that \(W\subseteq V(T)\) and \(|E(T)|\) is minimum. Vertices in \(W\) are called terminals. In this work, we design an algorithm for the enumeration of all Steiner \(W\)-trees for a constant number of terminals, which is the usual scenario in many applications. We discuss algorithmic issues involving space requirements to compactly represent the optimal solutions and the time delay to generate them. After generating the first Steiner \(W\)-tree in polynomial time, our algorithm enumerates the remaining trees with \(O(n)\) delay (where \(n=|V(G)|\)). An algorithm to enumerate all Steiner trees was already known (Khachiyan et al., SIAM J Discret Math 19:966–984, 2005), but this is the first one achieving polynomial delay. A by-product of our algorithm is a representation of all (possibly exponentially many) optimal solutions using polynomially bounded space. We also deal with the following problem: given \(W\) and a vertex \(x\in V(G)\setminus W\), is \(x\) in a Steiner \(W'\)-tree for some \(\varnothing \neq W' \subseteq W\)? This problem is investigated from the complexity point of view. We prove that it is NP-hard when \(W\) has arbitrary size. In addition, we prove that deciding whether \(x\) is in some Steiner \(W\)-tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs. Cited in 1 Document MSC: 90C35 Programming involving graphs or networks Keywords:complexity of algorithms; enumerative combinatorics; Steiner convexity; Steiner tree PDFBibTeX XMLCite \textit{M. C. Dourado} et al., Ann. Oper. Res. 223, 155--171 (2014; Zbl 1332.90326) Full Text: DOI References: [1] Betzler, N. (2006). Steiner tree problems in the analysis of biological networks. Master Thesis, Tübingen University. · Zbl 0688.05040 [2] Björklund, A., Husfeldt, T., Kaski, P. & Koivisto, M. (2007). Fourier meets Möbious: Fast subset convolution. In Proceedings of STOC 2007 (pp. 67-74). New York: ACM Press. · Zbl 1232.68188 [3] Cayley, A. (1889). A theorem on trees. Quarterly Journal of Mathematics, 23, 376-378. · JFM 21.0687.01 [4] Cáceres, J., Márquez, A., & Puertas, M. L. (2008). Steiner distance and convexity in graphs. European Journal of Combinatorics, 29, 726-736. · Zbl 1142.05021 [5] Chartrand, G., Oellermann, O. R., Tian, S., & Zou, H. B. (1989). Steiner distance in graphs. Časopis pro pěstováni matematiky a fysiky, 114, 399-410. · Zbl 0688.05040 [6] Dourado, M. C., Oliveira, R. A., & Protti, F. (2009). Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals. In textitLAGOS’09—V Latin-American graphs, algorithms and optimization symposium, Gramado, Brazil, november 2009. Electronic notes in discrete mathematics (Vol. 35, pp. 323-328). · Zbl 1268.05046 [7] Dreyfus, S. E., & Wagner, R. A. (1972). The Steiner problem in graphs. Networks, 1, 195-207. · Zbl 0229.05125 [8] Eppstein, D. (1995). Representing all minimum spanning trees with applications to counting and generation. Technical Report 95-50, Department of Information and Computer Science, University of California, Irvine, CA. Available at http://www.ics.uci.edu/ eppstein/pubs/Epp-TR-95-50, Accessed 27 Feb 2014. [9] Fomin, F. V., Grandoni, F. & Kratsch, D. (2008). Faster Steiner tree computation in polynomial-space. In Proceedings of the 16th annual European symposium on algorithms, Karlsruhe, Germany. Lecture notes in computer science (Vol. 5193, pp. 430-441). · Zbl 1158.68429 [10] Fomin, F. V., Grandoni, F., Kratsch, D., Lokshtanov, D., & Saurabh, S. (2013). Computing optimal Steiner trees in polynomial space. Algorithmica, 65, 584-604. · Zbl 1269.05049 [11] Gilbert, E. N., & Pollack, H. O. (1968). Steiner minimal trees. SIAM Journal on Applied Mathematics, 16, 1-29. · Zbl 0159.22001 [12] Hakimi, S. L. (1971). Steiner’s problem in graph and its implications. Networks, 1, 113-133. · Zbl 0229.05124 [13] Hwang, F. K., Richards, D. C., & Winter, P. (1992). The Steiner tree problem. Amsterdam: North-Holland. · Zbl 0774.05001 [14] Karp, RM; Miller, RE (ed.); Thatcher, JW (ed.), Reducibility among combinatorial problems, 85-103 (1972), New York [15] Khachiyan, L., Boros, E., Elbassioni, K., Gurvich, V., & Makino, K. (2005). On the complexity of some enumeration problems for matroids. SIAM Journal on Discrete Mathematics, 19, 966-984. · Zbl 1104.05017 [16] Kimelfeld, B. & Sagiv, Y. (2005). Efficiently enumerating results of keyword search. In Proceedings of the 10th international symposium DBLP, Trondheim, Norway. Lecture notes in computer science (Vol. 3774, pp. 58-73) · Zbl 1159.68421 [17] Lauer, P. E., & Szwarcfiter, J. L. (1976). A search strategy for the elementary cycles of a directed graph. BIT Numerical Mathematics, 16, 192-204. · Zbl 0331.68025 [18] Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1980). Generating all maximal independent sets: NP-hardness and polynomial time algorithms. SIAM Journal on Computing, 9, 558-565. · Zbl 0445.68054 [19] Levin, A. Y. (1971). Algorithm for shortest connection of a group of graph vertices. Soviet mathematics, Doklady, 12, 1477-1481. · Zbl 0243.05119 [20] Mölle, D., Richter, S., & Rossmanith, P. (2006). A faster algorithm for the Steiner tree problem. In Proceedings of STACS 2006 (pp. 561-570). · Zbl 1136.68468 [21] Nederlof, J. (2009). Fast polynomial-space algorithms using Möbius inversion: improving on Steiner tree and related problems. In Proceedings of ICALP 2009. Lecture notes in computer science (Vol. 5555, pp. 713-725). · Zbl 1248.68258 [22] Oellermann, O. R., & Puertas, M. L. (2007). Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs. Discrete Mathematics, 307, 88-96. · Zbl 1113.05030 [23] Prömel, H. J., & Steger, A. (2002). The Steiner tree problem: A tour through graphs, algorithms and complexity. Advanced lectures in mathematics. Braunschweig: Vieweg. [24] Smith, J. M., & Toppur, B. (1996). Euclidean Steiner minimal trees, minimum energy configurations, and the embedding problem of weighted graphs in \[E^3\] E3. Discrete Applied Mathematics, 71, 187-215. · Zbl 0881.92022 [25] Van de Vel, M. J. L. (1993). Theory of convex structures. Amsterdam: North-Holland. · Zbl 0785.52001 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.