[Model] SteinerTree

[zazabap]

Motivation

One of Karp's 21 NP-complete problems; foundational in network design. Telecommunications backbone routing, VLSI chip interconnect, pipeline network planning, and phylogenetic tree construction all reduce to Steiner Tree. Has known reductions to ILP and SAT. Opens a new network design category in the reduction graph.

Definition

Name: SteinerTree
Reference: Karp, 1972; Hwang, Richards & Winter, The Steiner Tree Problem, 1992

Given an undirected weighted graph $G = (V, E, w)$ where $w: E \to \mathbb{R}_{\geq 0}$, and a set of terminal vertices $T \subseteq V$, find a tree $S = (V_S, E_S)$ in $G$ such that $T \subseteq V_S$, minimizing the total edge weight:

$$\sum_{e \in E_S} w(e)$$

The vertices in $V_S \setminus T$ are called Steiner vertices — intermediate relay points that reduce total cost.

Variables

• Count: $m = |E|$ (one variable per edge)
• Per-variable domain: binary ${0, 1}$
• Meaning: $y_e = 1$ if edge $e$ is included in the Steiner tree

Schema (data type)

Type name: SteinerTree
Variants: graph Steiner tree, Euclidean Steiner tree, rectilinear Steiner tree

Field	Type	Description
graph	SimpleGraph	The weighted undirected graph $G = (V, E, w)$
terminals	Vec<usize>	The terminal vertex set $T \subseteq V$

Problem Size

Metric	Expression	Description
num_vertices	$n$	Number of vertices
num_edges	$m$	Number of edges
num_terminals	$\lvert T \rvert$	Number of terminal vertices

Complexity

• Decision complexity: NP-complete (Karp, 1972)
• Best known exact algorithm: $O(3^{|T|} \cdot n + 2^{|T|} \cdot n^2)$ via Dreyfus-Wagner dynamic programming over terminal subsets
• Approximation: 1.39-approximation (Byrka et al., 2013); the classic 2-approximation via minimum spanning tree of the terminal distance graph
• References: Karp 1972; Dreyfus & Wagner 1971; Byrka et al. 2013

Extra Remark

When $T = V$ (all vertices are terminals), the Steiner tree reduces to the minimum spanning tree (polynomial). The NP-hardness arises from choosing which Steiner vertices to include. Industry-standard tools include SteinLib (benchmark library) and GeoSteiner (exact solver for Euclidean instances). The rectilinear variant is critical in VLSI routing (Cadence, Synopsys).

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming, through a new SteinerTree → ILP rule issue (to be filed).

Bruteforce: enumerate all subsets of edges, check if terminals are connected and the selected edges form a tree, return minimum weight.

Example Instance

$n = 5$ vertices, $m = 7$ edges, terminals $T = {0, 2, 4}$:

    (2)     (2)
 0 ----- 1 ----- 2
          |       |
      (1) |       | (6)
          |       |
          3 ----- 4
             (1)

Also: $(0,3)$ weight 5, $(3,2)$ weight 5 (not shown for clarity).

Edge	Weight
$(0,1)$	2
$(1,2)$	2
$(1,3)$	1
$(3,4)$	1
$(0,3)$	5
$(3,2)$	5
$(2,4)$	6

Optimal Steiner tree: edges ${(0,1), (1,2), (1,3), (3,4)}$, cost $= 2+2+1+1 = 6$.

Steiner vertices used: ${1, 3}$. Vertex 1 acts as a hub connecting terminals 0 and 2; vertex 3 relays to terminal 4.

Compare: the only direct terminal-terminal edge is $(2,4)$ with weight 6 — equaling the entire Steiner tree cost by itself. This demonstrates why Steiner points are essential.