Steiner Forest via Union-Find and Primal-Dual

---

# 🎯 Steiner Forest via Union-Find and Primal-Dual

### physdes-py Implementation

@luk036 👨‍💻 · 2026 📅

---

### 📋 Agenda

**Part 1: Introduction** 🎯
- Problem Definition 🌲
- Steiner Tree vs Forest 🧩

**Part 2: Mathematical Foundations** 📐
- Primal LP — Cut Relaxation
- Dual LP — Moat Interpretation 🌊

**Part 3: Union-Find** 🔧
- Data Structure & Operations
- Visualization 🔍

**Part 4: PD-SF Algorithm** 🛠️
- Primal-Dual Approach
- Grid Example & Reverse Delete ✂️

]
.pull-right[

**Part 5: Implementation** 💻
- physdes-py Code
- Test Example 🧪

**Part 6: Proof Sketch** 📝
- Why ρ = 2

**Part 7: Experimental Validation** 📈
- Performance Results

**Part 8: Conclusion** 🔮
- Summary & Future Directions
- References 📚

]

---

### 📊 Figure: Steiner Forest Example (physdes-py Output)

![Steiner Forest](steiner_forest_simple.svg)

]
.pull-right[

**Example:** 4×4 grid with 2 terminal pairs

-   🔵 **Blue circles:** Sources (nodes 0, 3)
-   🔴 **Red circles:** Terminals (nodes 12, 15)
-   🟢 **Green circles:** Steiner nodes (1, 2, 4, 7, 8, 11)
-   **Total cost:** 9.0 units

]

---

## Part 1: Introduction & Problem Definition 🎯

---

### 🌲 What is the Steiner Forest Problem?

Given an undirected graph $G = ({\color{salmon} V}, {\color{lime} E})$ with non-negative edge weights ${\color{green} w_e} \geq 0$ and $k$ terminal pairs $({\color{green} s_i}, {\color{orange} t_i})$:

**Goal:** Find minimum-cost subset $F \subseteq E$ such that every pair $({\color{green} s_i}, {\color{orange} t_i})$ is connected in $({\color{salmon} V}, F)$.

.mermaid[
<pre>
graph TD
    subgraph "Input Graph"
        A[s] --> B
        B --> C[t]
        D[s] --> E
        E --> F[t]
    end
    subgraph "Steiner Forest"
        A1[Source] --> S[* Steiner]
        S --> T1[Target]
    end

style A fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style B fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style C fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style D fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style E fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style F fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style S fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px
</pre>
]

**NP-Hard** and **APX-Hard** 🎯

---

### 🧩 Steiner Tree vs. Steiner Forest

| Problem | Description | Example |
|---------|-------------|---------|
| **Steiner Tree** | Connect ALL terminals into ONE tree | Single connected component |
| **Steiner Forest** | Connect $k$ terminal pairs | Multiple independent trees |

.mermaid[
<pre>
graph TB
    subgraph "Steiner Tree (Single Tree)"
        direction TB
        S1["s₁"] === T1["t₁"]
        S2["s₂"] === T2["t₂"]
        S3["s₃"] === T3["t₃"]
    end

subgraph "Steiner Forest (Multiple Trees)"
        direction TB
        S1a["s₁"] --- T1a["t₁"]
        S2a["s₂"] --- T2a["t₂"]
        S3a["s₃"] --- T3a["t₃"]
    end

style S1 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style S2 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style S3 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style T1 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style T2 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style T3 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style S1a fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style S2a fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style S3a fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style T1a fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style T2a fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style T3a fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
</pre>
]

---

## Part 2: Mathematical Foundations 📐

---

### 📐 The Primal LP - Cut Relaxation (UCR)

**Variable:** ${\color{blue} x_e} \in \{0, 1\}$ for each edge $e \in E$

**Let $S_i$** = set of subsets $S \subseteq V$ separating terminals ${\color{green} s_i}$ and ${\color{orange} t_i}$

#### Primal Integer Program (IP)

$$
\begin{array}{ll}
\text{minimize} \quad & \sum_{e \in E} {\color{green} w_e} \, {\color{blue} x_e} \\
\text{subject to:} \quad & \sum_{e \in \delta(S)} {\color{blue} x_e} \geq 1, \quad \forall S \in S_i \text{ for some } i \\
& {\color{blue} x_e} \in \{0, 1\}, \quad \forall e \in E
\end{array}
$$

**Constraint (2):** Every cut separating a terminal pair must have at least one selected edge ✅

---

### 🌊 The Dual LP - Moat Interpretation

**Dual variables:** ${\color{orange} y_S} \geq 0$ for each cut $S$

#### Dual Program (LP)

$$
\begin{array}{ll}
\text{maximize} \quad & \sum_{S} {\color{orange} y_S} \\
\text{subject to:} \quad & \sum_{S: e \in \delta(S)} {\color{orange} y_S} \leq {\color{green} w_e}, \quad \forall e \in E \\
& {\color{orange} y_S} \geq 0, \quad \exists i : S \in S_i
\end{array}
$$

#### 🌊 Moat Metaphor

-   ${\color{orange} y_S}$ = width of a **moat** surrounding subset $S$
-   **Constraint (5):** Sum of moat widths crossing edge $e$ cannot exceed ${\color{green} w_e}$

---

### ⚖️ Complementary Slackness

**Primal-Dual Guiding Principle:**

$$
{\color{blue} x_e} = 1 \quad \implies \quad \sum_{S: e \in \delta(S)} {\color{orange} y_S} = {\color{green} w_e}
$$

**Key Insight:** Edge added to solution $F$ only when its dual constraint is **tight** (critical) 📌

---

## Part 3: Union-Find Data Structure 🔧

---

### 🔧 Union-Find (Disjoint Set Union)

Efficient data structure for tracking connected components with **path compression** and **union by rank**.

#### Operations

| Operation | Time Complexity | Description |
|-----------|---------------|-------------|
| `find(x)` | $O({\color{blue} \alpha}(n))$ | Find root/representative |
| `union(x, y)` | $O({\color{blue} \alpha}(n))$ | Merge two sets |

${\color{blue} \alpha}(n)$ = inverse Ackermann, practically constant

---

### physdes-py Implementation

```python
class UnionFind:
    """A Union-Find data structure with path compression and union by rank."""

def __init__(self, size: int):
        self.parent = list(range(size))
        self.rank = [0] * size

def find(self, idx: int) -> int:
        if self.parent[idx] != idx:
            self.parent[idx] = self.find(self.parent[idx])  # Path compression
        return self.parent[idx]

def union(self, idx1: int, idx2: int) -> bool:
        root1, root2 = self.find(idx1), self.find(idx2)
        if root1 == root2:
            return False
        # Union by rank
        if self.rank[root1] < self.rank[root2]:
            root1, root2 = root2, root1
        self.parent[root2] = root1
        if self.rank[root1] == self.rank[root2]:
            self.rank[root1] += 1
        return True
```

---

### 🔍 Visualizing Union-Find

.mermaid[
<pre>
graph TD
    subgraph "Initial State (5 components)"
        A0(0) --> A0
        B0(1) --> B0
        C0(2) --> C0
        D0(3) --> D0
        E0(4) --> E0
    end

subgraph "After union(0,1), union(2,3)"
        A1(0) --> B1(1)
        C1(2) --> D1(3)
    end

subgraph "After union(1,2) - Path Compression"
        A2(0) --> B2(1) --> C2(2) --> D2(3)
    end

style A0 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style B0 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style C0 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style D0 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style E0 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style A1 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style B1 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style C1 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style D1 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style A2 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style B2 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style C2 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style D2 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
</pre>
]

---

### Union-Find in PD-SF Algorithm

The algorithm uses Union-Find to track **connected components** during the primal-dual process:

| Iteration | Components | Action |
|-----------|------------|--------|
| 0 | {0}, {1}, {2}, {3}, ... | Each terminal separate |
| 1 | {0,1}, {2}, {3}, ... | Edge (0,1) added |
| 2 | {0,1,2}, {3}, ... | Edge (1,2) added |
| ... | ... | Continue until all connected |

**Key Insight:** Union-Find enables $O({\color{blue} \alpha}(n))$ component queries - essential for efficient algorithm! 📌

**Key optimizations:**

-   **Path compression:** Flatten tree during find
-   **Union by rank:** Attach smaller tree to larger

---

## Part 4: PD-SF Algorithm 🛠️

---

### 🛠️ Algorithm Overview

The **Primal-Dual Steiner Forest (PD-SF)** algorithm by Agrawal, Klein, and Ravi (1995)

#### Core Idea

1. **Initialize:** ${\color{orange} y} \leftarrow 0$, $F \leftarrow \emptyset$
2. **Iterate:** While unconnected pairs exist:
   -   Identify **active components** (components containing terminals needing connection)
   -   **Increase dual variables** uniformly for all active components
   -   When edge becomes **tight**, add it to $F$
3. **Prune:** Reverse-delete to remove redundant edges

.mermaid[
<pre>
flowchart LR
    A["1. Init: y=0, F={}"] --> B{"2. While ∃ unconnected pairs"}
    B -->|"Yes"| C["Identify Active Components"]
    C --> D["Increase y_C uniformly"]
    D --> E{"Edge becomes tight?"}
    E -->|"Yes"| F["Add e to F"]
    F --> G["Update Components"]
    G --> B
    B -->|"No"| H["3. Reverse Delete"]
    H --> I["Return Forest F'"]

style A fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style B fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style C fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px
    style D fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px
    style E fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
    style F fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style G fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style H fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style I fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
</pre>
]

---

### 📊 Algorithm Step-by-Step

#### Step 1: Active Components

A component $C$ is **active** if it contains at least one terminal that needs to connect to a terminal in a different component.

```python
# Compute active components
for root, terms in comp_terms.items():
    is_active = False
    for terminal in terms:
        for partner in pair_dict[terminal]:
            if term_root[partner] != root:
                is_active = True
                break
    if is_active:
        active_comps.add(root)
```

---

#### Step 2: Dual Ascent

Increase **all active components' dual variables uniformly** until an edge becomes tight:

$$
\Delta_e = \frac{{\color{green} c_e} - \text{paid}(e)}{\text{num\_active}(e)}
$$

```python
# Find minimum delta
min_delta = min(Δ_e for all crossing edges)
paid[e] += min_delta * num_active(e)
```

#### Step 3: Edge Selection

When an edge becomes tight (paid = cost), add it to the forest:

```python
if paid[edge] >= cost:
    F.append((u, v, cost))
    uf.union(u, v)  # Merge components
```

---

### 🔄 Grid Graph Example

.mermaid[
<pre>
graph TD
    subgraph "Grid Graph (h×w)"
        N00(0,0) --- N01(0,1) --- N02(0,2)
        N00 --- N10(1,0) --- N11(1,1)
        N01 --- N11 --- N12(1,2)
        N10 --- N11 --- N20(2,0)
    end

style N00 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style N01 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style N02 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style N10 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style N11 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style N12 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style N20 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
</pre>
]
]
.pull-right[

#### Edge Generation

```python
for row in range(height):
    for col in range(width):
        node = row * width + col
        if col + 1 < width:
            edges.append((node, node + 1, 1.0))  # Horizontal
        if row + 1 < height:
            edges.append((node, node + width, 1.0))  # Vertical
```

]

---

### ✂️ Reverse Delete (Pruning)

After all pairs connected, remove redundant edges in **reverse order of addition**:

```python
F_pruned = F[:]
for idx in range(len(F) - 1, -1, -1):
    temp_uf = UnionFind(n)
    for jdx in range(len(F)):
        if jdx != idx:
            temp_uf.union(F[jdx][0], F[jdx][1])
    # Check if all pairs still connected
    if all(temp_uf.find(s) == temp_uf.find(t) for s, t in pairs):
        del F_pruned[idx]  # Safe to remove
```

#### Why This Works

> If edge $e$ created a cycle, removing $e$ doesn't disconnect any terminal pair. The last-added edge in any cycle is always redundant!

---

### 📊 Large-Scale Example (150 pairs on 20×20 grid)

.pull-left[
![Steiner Forest Large](steiner_forest_large.svg)
]
.pull-right[
-   **Grid size:** 20×20 (400 nodes)
-   **Terminal pairs:** 150
-   **Total cost:** 233.0
-   **Steiner nodes inserted:** 27
]

---

## Part 5: Implementation Deep Dive 💻

---

### 💻 physdes-py Code Structure

From `src/physdes/steiner_forest/steiner_forest_grid.py`:

---

#### Class: UnionFind

```python
class UnionFind:
    """
    A Union-Find data structure with path compression and union by rank.
    Commonly used in graph algorithms like Kruskal's MST.
    """

def __init__(self, size: int):
        self.parent: List[int] = list(range(size))
        self.rank: List[int] = [0] * size

def find(self, idx: int) -> int:
        if self.parent[idx] != idx:
            self.parent[idx] = self.find(self.parent[idx])
        return self.parent[idx]

def union(self, idx1: int, idx2: int) -> bool:
        root1, root2 = self.find(idx1), self.find(idx2)
        if root1 == root2:
            return False
        if self.rank[root1] < self.rank[root2]:
            root1, root2 = root2, root1
        self.parent[root2] = root1
        if self.rank[root1] == self.rank[root2]:
            self.rank[root1] += 1
        return True
```

---

#### Function: steiner_forest_grid

```python
def steiner_forest_grid(
    height: int,
    width: int,
    pairs: List[Tuple[Tuple[int, int], Tuple[int, int]]]
) -> Tuple[List[Tuple[int, int, float]], float, Set[int], Set[int], Set[int]]:
    """
    Computes an approximate Steiner forest on a grid graph.

The algorithm is based on the primal-dual approach for the Steiner
    network problem. It iteratively pays for edges until all terminal
    pairs are connected.
    """
    n = height * width
    uf = UnionFind(n)

# Build source/terminal sets
    sources, terminals = set(), set()
    pair_dict = defaultdict(list)
    for (sx, sy), (tx, ty) in pairs:
        source_idx = sx * width + sy
        target_idx = tx * width + ty
        sources.add(source_idx)
        terminals.add(target_idx)
        pair_dict[source_idx].append(target_idx)
        pair_dict[target_idx].append(source_idx)
```

---

#### Main Loop

```python
paid = defaultdict(float)
F = []

while True:
    # Check if all pairs connected
    term_root = {t: uf.find(t) for t in all_terminals}
    if all(term_root[s] == term_root[t] for s, ts in pair_dict.items() for t in ts):
        break  # Feasible solution found

# Find active components and minimum delta
    min_delta = float('inf')
    for u, v, cost in edges:
        if uf.find(u) == uf.find(v):
            continue
        num_active = (uf.find(u) in active_comps) + (uf.find(v) in active_comps)
        if num_active == 0:
            continue
        delta = (cost - paid[(u, v)]) / num_active
        min_delta = min(min_delta, delta)

# Update payments and add edges
    for u, v, cost in edges:
        if uf.find(u) != uf.find(v):
            paid[(u, v)] += min_delta * num_active
            if paid[(u, v)] >= cost:
                F.append((u, v, cost))
                uf.union(u, v)
```

---

#### Complete Function Signature

```python
def steiner_forest_grid(
    height: int,
    width: int,
    pairs: List[Tuple[Tuple[int, int], Tuple[int, int]]]
) -> Tuple[
    List[Tuple[int, int, float]],  # F_pruned: edges in forest
    float,                          # total_cost
    Set[int],                      # sources
    Set[int],                      # terminals
    Set[int]                       # steiner_nodes (non-terminal nodes in forest)
]:
```

#### Return Values

| Return | Description |
|--------|-------------|
| `F_pruned` | List of edges $(u, v, cost)$ in final forest |
| `total_cost` | Sum of all edge costs |
| `sources` | Set of source node indices |
| `terminals` | Set of terminal node indices |
| `steiner_nodes` | Non-terminal nodes used in forest |
]

---

### 🧪 Test Example

```python
>>> h, w = 2, 2
>>> pairs = [((0, 0), (1, 1))]
>>> F_pruned, cost, sources, terminals, steiners = steiner_forest_grid(h, w, pairs)
>>> sorted(F_pruned)
[(0, 1, 1.0), (1, 3, 1.0)]
>>> cost
2.0
>>> sources, terminals, steiners
({0}, {3}, {1})
```

Visual:

```text
Grid (2×2)          Steiner Forest
.---.---.         o---*---o
| S |   |    ==>    |     |
'---'---'         '---'---'
|   | T |         |   *   |
'---'---'         '---'---o
                   S     T
```

---

## Part 6: Proof Sketch — Why ρ = 2 📝

---

### 📝 The 2-Approximation Theorem

**Theorem (Agrawal, Klein, Ravi, 1995):**
The PD-SF algorithm returns a feasible Steiner forest $F'$ with

$$
c({\color{blue} F'}) \leq 2 \cdot {\color{red} \text{OPT}}
$$

#### Key Steps in Proof

1. **Dual as Lower Bound:** $\sum_S {\color{orange} y_S} \leq {\color{red} \text{OPT}}$
2. **Cost Decomposition:** $c({\color{blue} F'}) = \sum_S {\color{orange} y_S} \cdot |{\color{blue} F'} \cap \delta(S)|$
3. **Critical Lemma:** $|{\color{blue} F'} \cap \delta(S)| \leq 2$ for active components
4. **Forest Property:** After reverse-delete, ${\color{blue} F'}[A_t]$ is acyclic $\implies$ max degree ≤ 2

---

### 🔑 Critical Lemma

**Lemma:** For any iteration $t$, with active components $A_t$:

$$
\sum_{C \in A_t} |{\color{blue} F'} \cap \delta(C)| \leq 2|A_t|
$$

#### Proof Sketch

-   After **reverse delete**, $F'[A_t]$ forms a **forest** (acyclic)
-   In any forest, sum of degrees $\leq 2 \times$ \# vertices
-   Since each component $C \in A_t$ has at least degree 1 (leaf), the sum is bounded

.mermaid[
<pre>
graph TD
    subgraph "Forest Property"
        C1(C₁) --- C2(C₂)
        C2 --- C3(C₃)
    end

style C1 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style C2 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style C3 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
</pre>
]

**Degree** [C₁] = 1, [C₂] = 2, [C₃] = 1 → **Sum = 4 ≤ 2×3 = 6** ✅

---

### 📊 Complete Cost Bound

By induction over iterations:

$$
c({\color{blue} F'}) = \sum_t \Delta_t \cdot \sum_{C \in A_t} |{\color{blue} F'} \cap \delta(C)|
$$

$$
\leq \sum_t \Delta_t \cdot 2|A_t| = 2 \sum_t \Delta_t |A_t|
$$

$$
= 2 \sum_S {\color{orange} y_S} \leq 2 \cdot {\color{red} \text{OPT}}
$$

**Q.E.D.** 🎉

---

## Part 7: Experimental Validation 📈

---

### 📈 Performance Results

From the physdes-py test suite on SteinForestLib:

| Metric | PD-SF | Greedy | Randomized |
| -------- | ------- | ------- | ------- |
| **Theoretical Ratio** | 2 | $\Omega(\log n)$ | $O(\log n)$ |
| **Worst Observed** | 1.269 | 1.115 | 7.086 |
| **Runtime** | Fastest | Moderate | Slow |

#### Key Observations

-   ✅ **PD-SF is 1-3 orders of magnitude faster** than alternatives
-   ✅ **Near-optimal solutions** (observed ratio ~1.27)
-   ✅ **Runtime independent** of terminal count $k$

---

### 🔬 physdes-py Test Results

```python
>>> h, w = 8, 8
>>> pairs = [((0, 0), (3, 2)), ((0, 0), (0, 5)), ...]
>>> F, cost, sources, terminals, steiners = steiner_forest_grid(h, w, pairs)
>>> cost
17.0  # Observed vs OPT ≈ 15-17
```

#### Large-Scale Test (150 pairs on 20×20 grid)

```text
Total cost: 233.0
Sources: 150 unique sources
Terminals: 150 unique terminals
Steiner nodes: 27 inserted
```

---

## Part 8: Conclusion & Future Directions 🔮

---

### 🎯 Summary

| Aspect | PD-SF |
|--------|-------|
| **Approximation Ratio** | 2 (tight) |
| **Time Complexity** | $O(mn)$ |
| **Space Complexity** | $O(n + m)$ |
| **Key Innovation** | Primal-Dual + Reverse Delete |

#### Contributions

1. **First constant-factor approximation** for Steiner Forest
2. **Simple, efficient** algorithm suitable for practice
3. **Theoretical foundation** for modern network design

---

### 🔮 Future Directions

#### Open Problems

-   **Beat 2:** Can we achieve $2 - \epsilon$ approximation?
-   **LP Gaps:** Investigate Bidirected Cut Relaxation (Forest-BCR)
-   **Practical Improvements:** Better primal heuristics + LP rounding

#### Related Work

-   **Bykowski et al. (2024):** $2 - 10^{-11}$ approximation - breaking the barrier!
-   **Reinforcement Learning:** New ML-guided approaches emerging

#### physdes-py Extensions

-   Diagonal edges support
-   3D grid generalization
-   Integration with Global Router

---

### 📚 References

1. **Agrawal, Klein, Ravi (1995)** - "When is the Steiner Problem Easy?"
2. **Goemans & Williamson (1995)** - Improved primal-dual techniques
3. **Bykowski et al. (2024)** - $2 - 10^{-11}$ breakthrough
4. **physdes-py** - <https://github.com/luk036/physdes-py>

---

# 🙋 Q&A

### Questions? Discussion? 💬

-   📧 Contact: physdes-py maintainers
-   🌐 GitHub: github.com/luk036/physdes-py
-   📖 Docs: physdes-py.readthedocs.io

---

# 👏 Thank You

### Steiner Forest via Union-Find and Primal-Dual

```python
# Run the example!
if __name__ == "__main__":
    from physdes.steiner_forest.steiner_forest_grid import steiner_forest_grid

h, w = 20, 20
    pairs = [((i, j), (h-i-1, w-j-1)) for i in range(10) for j in range(15)]
    F, cost, sources, terminals, steiners = steiner_forest_grid(h, w, pairs)
    print(f"Cost: {cost}, Steiner nodes: {len(steiners)}")
```

Slides built with Remark.js 🎉 | KaTeX 📐 | Mermaid 🧩 | Nord Theme 🌙