Separator-Based Pruned Dynamic Programming for Steiner Tree

  • Yoichi Iwata National Institute of Informatics
  • Takuto Shigemura The University of Tokyo

Abstract

Steiner tree is a classical NP-hard problem that has been extensively studied both theoretically and empirically. In theory, the fastest approach for inputs with a small number of terminals uses the dynamic programming, but in practice, stateof-the-art solvers are based on the branch-and-cut method. In this paper, we present a novel separator-based pruning technique for speeding up a theoretically fast DP algorithm. Our empirical evaluation shows that our pruned DP algorithm is quite effective against real-world instances admitting small separators, scales to more than a hundred terminals, and is competitive with a branch-and-cut solver.

Published
2019-07-17
Section
AAAI Technical Track: Constraint Satisfaction and Optimization