A solver for the Steiner tree problem with few terminals

Abstract

Das graphentheoretische Steinerbaumproblem ist ein sehr bekanntes NP-hartes Problem. Instanzen des Problems bestehen aus einem Graphen G = (V, E), den Kosten für Kanten c und einer Menge aus Terminalen R \subseteq V. Die Lösung zu einer Instanz ist ein zusammenhängender Teilgraph minimalen Gewichts der alle Terminale enthält. Es ist lange bekannt, dass Instanzen mit einer Laufzeitbeschränkung von O(3 |R|) gelöst werden können. Das Problem ist also effizient lösbar, wenn die Anzahl der Terminale beschränkt werden kann. PACE ist ein alljährlicher Wettbewerb. Jedes Jahr wird ein anderes NP-hartes Problem verwendet, von dem bekannt ist, dass es effizient lösbar ist, wenn ein Parameter beschränkt werden kann. Die TeilnehmerInnen geben für diesen Wettbewerb Programme ab, die Instanzen des Problems lösen können (Lösungsprogramme). Diese werden danach gereiht, wie viele Instanzen sie innherhalb einer gewissen Zeitund Arbeitsspeichergrenze lösen können. Dieses Jahr war das ausgeschriebene Problem das graphentheoretische Steinerbaumproblem. Wir haben ein Lösungsprogramm implementiert und damit den vierten Platz erzielt. In dieser Arbeit präsentieren wir den formaltheoretischen Hintergrund sowie Implementierungsdetails unseres Programms. Der Großteil der Implementierung folgt direkt aus der Theorie. Daher beschränken wir uns auf jene Implementierungsdetails die entweder spezifisch für unser Programm sind, oder nicht direkt aus der Theorie ableitbar sind. Der Quellcode aller teilnehmenden Programme muss nach der Abgabefrist veröffentlicht werden. Dies hat uns erlaubt die drei besten Programme näher zu analysieren. Wir präsentieren hier die wesentlichen Unterschiede zwischen diesen Programmen und unserem. Wir haben außerdem versucht, das durch die Analysen gesammelte Wissen, in unser Programm einzubauen. Wie diese Adaptierungen unser Programm beeinflusst haben, ist ein weiteres Thema dieser Arbeit. Wir haben unser Programm außerdem mit öffentlichen und bekannten Instanzen getestet. Wir präsentieren die Ergebnisse und vergleichen diese mit den von anderen aktuellen Lösungsprogrammen erzielten Resultaten.

The Steiner tree problem on graphs is a well known NP-hard problem. Instances of this problem define a graph G = (V, E) with edge costs and a set of terminals R \subseteq V. The solution to an instance is a connected subgraph of minimal total cost, that contains all vertices in R. It is known that an instance can be solved in time O(3 |R|). The problem is therefore (fixed parameter) tractable if we know that the number of terminals is smaller than some k. PACE is an annual competition. Each year a different fixed parameter tractable problem is used. Participants submit programs that solve instances of the problem. These solvers are then ranked by the number of instances they could solve within a given time and memory limit. This year's topic was the Steiner tree problem on graphs. We implemented and submitted a solver that placed 4th in the competition. In this thesis we discuss the formal theory used in our solver, as well as implementation details. Since most of the implementation follows directly from the theory, we focus on details that are particular to our implementation or not apparent from theory. PACE requires the source code of all submitted solvers to be publicly available. This allowed us to analyze the top three submissions. We discuss how they differ from our implementation. We also tried to apply the insights from this analysis to our solver. We show if and how these extensions impact the performance of our implementation. We benchmarked our solver against a collection of publicly available and well known instances. We present the results and discuss how these compare to those of other state-of-the-art solvers.