Cost-constrained Minimal Steiner Tree Enumeration

The Steiner tree enumeration problem is a well-known problem that asks for enumerating Steiner trees. Although numerous theoretical works proposed algorithms for the problem and analyzed their complexity, there are no practical algorithms and empirical studies. In this paper, we first study the Steiner tree enumeration problem practically. First, we define a practical problem cost-constrained minimal Steiner tree enumeration problem, which enumerates minimal Steiner trees with costs not larger than a given threshold. Second, to address the problem, we propose a binary decision diagram (BDD)-based algorithm. The BDD-based algorithm constructs a BDD that compactly represents the set of minimal Steiner trees and then traverses the BDD for enumeration. We develop a novel frontier-based algorithm to construct such BDDs efficiently. Furthermore, we extend our algorithm to be scalable for large-scale graphs by preprocessing the given graph and controlling the number of generated Steiner trees to reduce memory and computation costs. We validate that our algorithm can efficiently enumerate minimal Steiner trees in real-world graphs.