Algorithmic aspects of Steiner convexity and enumeration of Steiner trees

作者：Dourado Mitre C; Oliveira Rodolfo A; Protti Fabio^*

来源：Annals of Operations Research, 2014, 223(1): 155-171.

DOI：10.1007/s10479-014-1607-5

• Complexity of algorithms
• Enumerative combinatorics
• Steiner convexity
• Steiner tree

For a set of vertices of a connected graph , a Steiner W-tree is a connected subgraph of such that and is minimum. Vertices in are called terminals. In this work, we design an algorithm for the enumeration of all Steiner -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 -tree in polynomial time, our algorithm enumerates the remaining trees with delay (where ). 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 and a vertex , is in a Steiner -tree for some ? This problem is investigated from the complexity point of view. We prove that it is NP-hard when has arbitrary size. In addition, we prove that deciding whether is in some Steiner -tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs.

• 出版日期2014-12