Hadlock's Algorithm for Planar MAX-CUT

---

# 🧩 Hadlock's Algorithm for Planar MAX-CUT

## From MAX-CUT to Minimum Weight Perfect Matching 🎯

@luk036 👨‍💻 · 2026 📅

---

### 📋 Agenda

### 🧠 Concepts

1. The MAX-CUT Problem
2. Planar Graphs & Their Properties
3. Hadlock's Key Insight
4. Dual Graph Construction
5. Odd Faces & Why They Matter
6. All-Pairs Shortest Paths
7. Minimum Weight Perfect Matching
8. Recovering the Maximum Cut

]

### ⚡ Optimization

9. **Biconnected Component (BC) Speedup**
10. Walkthrough Examples
11. Python Implementation
12. C++ Implementation
13. Complexity Analysis
14. Key Takeaways

]

---

## 🎯 The MAX-CUT Problem

---

### What is MAX-CUT? 🤔

**Definition:** Given a graph $G = (V, E)$ with edge weights $w: E \to \mathbb{R}^+$, partition $V$ into two sets $(S, V \setminus S)$ to **maximize** the total weight of edges crossing between the sets.

$$ \text{MAX-CUT}(G) = \max_{S \subseteq V} \sum_{\substack{u \in S \\ v \notin S}} w(u, v) $$

<pre>
graph LR
    subgraph S["Set S"]
        A(("A"))
        B(("B"))
    end
    subgraph V_S["Set V \ S"]
        C(("C"))
        D(("D"))
    end
    A ===|"5 ✓"| C
    A -..-|"3 ✓"| D
    B ===|"7 ✓"| C
    B -..-|"2 ✓"| D
    linkStyle 0 stroke:#4caf50,stroke-width:3px
    linkStyle 1 stroke:#4caf50,stroke-width:3px
    linkStyle 2 stroke:#4caf50,stroke-width:3px
    linkStyle 3 stroke:#4caf50,stroke-width:3px
    style A fill:#e3f2fd,stroke:#1565c0
    style B fill:#e3f2fd,stroke:#1565c0
    style C fill:#fce4ec,stroke:#c62828
    style D fill:#fce4ec,stroke:#c62828
    style S fill:#e3f2fd,color:#1565c0
    style V_S fill:#fce4ec,color:#c62828
</pre>

]

> **Key property:** Every cut corresponds to a bipartition of the vertex set.

---

### MAX-CUT Complexity 📊

| Graph Class    | Complexity          | Algorithm                    |
| -------------- | ------------------- | ---------------------------- |
| **General**    | NP-hard 🚫          | Goemans-Williamson (SDP) 📐  |
| **Planar** 🟢  | Polynomial ✅        | **Hadlock (1975)** 🎉        |
| **Bipartite**  | Trivial (all edges) | Every edge is in the cut     |

**Hadlock's breakthrough** (1975):
> *"Finding a Maximum Cut of a Planar Graph in Polynomial Time"*
> — SIAM Journal on Computing, 4(3), 221-225 📄

The key: **Planar graphs** have a dual graph structure that enables a polynomial reduction.

---

## 🗺️ Planar Graphs & Their Embeddings

---

### What Makes a Graph Planar? 🟢

A graph is **planar** if it can be drawn on a sphere (or plane) without edge crossings.

<pre>
graph LR
    subgraph Planar["✅ Planar"]
        K4(("K₄"))
    end
    K4 --- 2(( ))
    K4 --- 3(( ))
    K4 --- 4(( ))
    2 --- 3
    2 --- 4
    3 --- 4
    style Planar fill:#e8f5e9,color:#2e7d32
    style K4 fill:#c8e6c9,stroke:#2e7d32
    style 2 fill:#c8e6c9,stroke:#2e7d32
    style 3 fill:#c8e6c9,stroke:#2e7d32
    style 4 fill:#c8e6c9,stroke:#2e7d32
</pre>

]
]

<pre>
graph LR
    subgraph NonPlanar["🚫 Non-Planar"]
        K5(("K₅"))
    end
    K5 --- B(( ))
    K5 --- C(( ))
    K5 --- D(( ))
    K5 --- E(( ))
    B --- C
    B --- D
    B --- E
    C --- D
    C --- E
    D --- E
    style NonPlanar fill:#fce4ec,color:#c62828
    style K5 fill:#ffcdd2,stroke:#c62828
    style B fill:#ffcdd2,stroke:#c62828
    style C fill:#ffcdd2,stroke:#c62828
    style D fill:#ffcdd2,stroke:#c62828
    style E fill:#ffcdd2,stroke:#c62828
</pre>

]
]

**Planar graphs exclude** 
- $K_5$ (complete graph on 5 vertices) and
- $K_{3,3}$ (complete bipartite 3+3)

as minors.

---

### Planar Embedding & Faces 😊

A **planar embedding** divides the plane into connected regions called **faces**.

<pre>
graph LR
    0((0)) ---|"a"| 1((1))
    1 ---|"b"| 2((2))
    2 ---|"c"| 0
    2 ---|"d"| 3((3))
    3 ---|"e"| 4((4))
    4 ---|"f"| 2
    style 0 fill:#bbdefb,stroke:#1565c0
    style 1 fill:#bbdefb,stroke:#1565c0
    style 2 fill:#bbdefb,stroke:#1565c0
    style 3 fill:#bbdefb,stroke:#1565c0
    style 4 fill:#bbdefb,stroke:#1565c0
    linkStyle 0 stroke:#1565c0,stroke-width:2px
    linkStyle 1 stroke:#1565c0,stroke-width:2px
    linkStyle 2 stroke:#1565c0,stroke-width:2px
    linkStyle 3 stroke:#1565c0,stroke-width:2px
    linkStyle 4 stroke:#1565c0,stroke-width:2px
    linkStyle 5 stroke:#1565c0,stroke-width:2px
</pre>

]

- **Face 0** (inner): $(1, 2, 3, 4)$ — boundary walk of triangle 1-2-3 + edge 3-4 + edge 4-2
- **Face 1** (inner): $(0, 1, 2)$ — triangle with 3 edges
- **Face 2** (outer): $(0, 2, 4, 3, 2, 1)$ — the unbounded region

> Each face is a **cyclic sequence** of nodes. The outer face is just another face! 🌍

---

## 🧩 Hadlock's Algorithm — Step by Step

---

### Algorithm Overview 🔄

Hadlock reduces MAX-CUT on planar graphs to **Minimum Weight Perfect Matching (MWPM)** on a complete graph of odd faces.

<pre>
flowchart LR
    A["1. Find Planar\nEmbedding"] --> B["2. Build Dual\nGraph"]
    B --> C["3. Identify\nOdd Faces"]
    C --> D["4. All-Pairs Shortest\nPaths in Dual"]
    style A fill:#e3f2fd,stroke:#1565c0
    style B fill:#bbdefb,stroke:#1565c0
    style C fill:#fff9c4,stroke:#f9a825
    style D fill:#e8f5e9,stroke:#2e7d32
</pre>

]

<pre>
flowchart LR
    E["5. Complete Graph of\nOdd Faces + MWPM"] --> F["6. Excluded Edges\n from Matching Paths"]
    F --> G["7. Max Cut = All Edges\n setminus Excluded"]
    style E fill:#fce4ec,stroke:#c62828
    style F fill:#f3e5f5,stroke:#7b1fa2
    style G fill:#e8f5e9,stroke:#2e7d32,stroke-width:3px
</pre>

]

---

### Step 1: Planar Embedding 🗺️

Use `nx.check_planarity(G)` to verify planarity and get the embedding.

```python
is_planar, embedding = nx.check_planarity(G)
if not is_planar:
    raise nx.NetworkXException("Graph is not planar")
```

The embedding gives us **half-edge traversals** to walk face boundaries:

```python
def _find_faces(embedding):
    visited = set()
    faces = []
    for v in embedding.nodes():
        for w in embedding.neighbors(v):
            if (v, w) in visited: continue
            mark = set()
            face_nodes = list(embedding.traverse_face(v, w, mark))
            visited.update(mark)
            faces.append(face_nodes)
    return faces
```

---

### Step 2: Dual Graph Construction 🔗

Each **face** becomes a **dual vertex**. Two dual vertices connect if the corresponding faces share a primal edge.

<pre>
graph TD
    subgraph Primal["Primal Graph"]
        1((1)) --- 2((2))
        2 --- 3((3))
        3 --- 4((4))
        4 --- 1
        1 --- 3
    end
    subgraph Dual["Dual Graph"]
        Fa(((Fₐ)))
        Fb(((F_b)))
        Fc(((F_c)))
        Fa === Fb
        Fb === Fc
        Fa === Fc
    end
    style Primal fill:#e3f2fd
    style Dual fill:#fce4ec
    style Fa fill:#ffcdd2,stroke:#c62828
    style Fb fill:#ffcdd2,stroke:#c62828
    style Fc fill:#ffcdd2,stroke:#c62828
    style 1 fill:#bbdefb,stroke:#1565c0
    style 2 fill:#bbdefb,stroke:#1565c0
    style 3 fill:#bbdefb,stroke:#1565c0
    style 4 fill:#bbdefb,stroke:#1565c0
    linkStyle 0 stroke:#1565c0,stroke-width:2px
    linkStyle 1 stroke:#1565c0,stroke-width:2px
    linkStyle 2 stroke:#1565c0,stroke-width:2px
    linkStyle 3 stroke:#1565c0,stroke-width:2px
    linkStyle 4 stroke:#1565c0,stroke-width:2px
</pre>

]

Dual edges store:
- **weight:** weight of the shared primal edge
- **primal:** the $(u, v)$ tuple of the shared primal edge

> If two faces share multiple edges, only the **minimum weight** connection is kept.

---

### Step 3: Odd Faces 🟡

A face is **odd** if its boundary has an odd number of edges.

$$ \text{odd}(F_i) \iff |F_i| \bmod 2 = 1 $$

<pre>
graph TD
    subgraph Faces["Triangle Faces (Both Odd)"]
        T1[("F₀: (0,1,2)\n3 edges")]
        T2[("F₁: (0,2,1)\n3 edges")]
    end
    T1 -.- T2
    style Faces fill:#fff9c4
    style T1 fill:#fff9c4,stroke:#f9a825,stroke-width:3px
    style T2 fill:#fff9c4,stroke:#f9a825,stroke-width:3px
</pre>

]

**Why odd faces?** 🤔
- A cut $S$ induces a bipartition of each face's boundary
- An **even** face can be properly 2-colored (alternating in/out of cut)
- An **odd** face **cannot** — at least one edge must be **excluded** from the cut
- The odd faces are exactly the "frustrated" constraints

> **Handshaking Lemma:** Planar graphs always have an **even** number of odd faces.

---

### Step 4: All-Pairs Shortest Paths 🚀

Compute shortest path distances between all pairs of **odd faces** in the dual graph.

$$ d_{ij} = \text{shortest path distance between odd face } i \text{ and odd face } j $$

```python
dist = dict(nx.all_pairs_dijkstra_path_length(du_G, weight="weight"))
paths = dict(nx.all_pairs_dijkstra_path(du_G, weight="weight"))
```

The weight of a dual edge = weight of the shared primal edge. A shortest path in the dual corresponds to a **min-weight set of primal edges** connecting two faces.

<pre>
graph TD
    subgraph Dual2["Dual Graph"]
        Fa(((Fₐ))) -- "w=2" --- Fb(((F_b)))
        Fb -- "w=3" --- Fc(((F_c)))
        Fa -- "w=5" --- Fc
    end
    style Fa fill:#ffcdd2,stroke:#c62828,stroke-width:3px
    style Fb fill:#ffcdd2,stroke:#c62828,stroke-width:3px
    style Fc fill:#ffcdd2,stroke:#c62828,stroke-width:3px
    style Dual2 fill:#fce4ec
</pre>

]

$$ d_{F_a, F_c} = \min(5,\ 2 + 3) = 5 $$

---

### Step 5: MWPM on Odd Faces 💍

Construct a **complete graph** on the odd-face vertices with edge weights = shortest-path distances.

Find a **minimum weight perfect matching** (MWPM):

```python
complete_odd = nx.Graph()
complete_odd.add_nodes_from(odd_faces)
for i in range(len(odd_faces)):
    for j in range(i + 1, len(odd_faces)):
        u, v = odd_faces[i], odd_faces[j]
        complete_odd.add_edge(u, v, weight=dist[u][v])

matching = nx.algorithms.matching.min_weight_matching(complete_odd)
```

<pre>
graph LR
    Fa(((Fₐ))) -- "d=5" --- Fb(((F_b)))
    Fa -- "d=3" --- Fc(((F_c)))
    Fb -- "d=4" --- Fc
    style Fa fill:#ffcdd2,stroke:#c62828,stroke-width:3px
    style Fb fill:#ffcdd2,stroke:#c62828,stroke-width:3px
    style Fc fill:#ffcdd2,stroke:#c62828,stroke-width:3px
    linkStyle 0 stroke:#bdbdbd,stroke-width:2px
    linkStyle 1 stroke:#4caf50,stroke-width:4px
    linkStyle 2 stroke:#bdbdbd,stroke-width:2px
</pre>

]
]
.pull-right[
> Matching pairs $(F_a, F_c)$ with distance $3$ is the minimum weight matching.
]

---

### Step 6: From Matching to Excluded Edges 🧵

For each matched pair $(u, v)$ of odd faces, walk the shortest path in the dual. The **primal edges** along those paths are the **excluded** edges.

```python
excluded = set()
for u, v in matching:
    path = paths[u][v]
    for k in range(len(path) - 1):
        primal_edge = du_G[path[k]][path[k + 1]].get("primal")
        if primal_edge is not None:
            excluded.add(tuple(sorted(primal_edge)))
```

<pre>
graph TD
    subgraph DualPath["Dual Path: Fa → Fb → Fc"]
        Fa(((Fₐ))) -- "primal: (1,3)" --> Fb(((F_b)))
        Fb -- "primal: (3,4)" --> Fc(((F_c)))
    end
    style Fa fill:#ffcdd2,stroke:#c62828
    style Fb fill:#ffcdd2,stroke:#c62828
    style Fc fill:#ffcdd2,stroke:#c62828
    style DualPath fill:#f3e5f5
</pre>

]

**Excluded primal edges:** $(1,3)$ and $(3,4)$ 🚫

---

### Step 7: The Maximum Cut 🏆

$$ \text{MAX-CUT} = \{\text{all primal edges}\} \setminus \{\text{excluded edges}\} $$

```python
all_edges = {tuple(sorted(e)) for e in G.edges()}
return all_edges - excluded
```

<pre>
graph LR
    1((1)) -- "✓" --- 2((2))
    2 -- "✓" --- 3((3))
    3 -- "✗" --- 4((4))
    4 -- "✓" --- 1
    1 -- "✗" --- 3
    style 1 fill:#e3f2fd,stroke:#1565c0
    style 2 fill:#fce4ec,stroke:#c62828
    style 3 fill:#fce4ec,stroke:#c62828
    style 4 fill:#e3f2fd,stroke:#1565c0
    linkStyle 0 stroke:#4caf50,stroke-width:3px
    linkStyle 1 stroke:#4caf50,stroke-width:3px
    linkStyle 2 stroke:#f44336,stroke-width:3px
    linkStyle 3 stroke:#4caf50,stroke-width:3px
    linkStyle 4 stroke:#f44336,stroke-width:3px
</pre>

]

> The excluded edges (red) are removed. Remaining edges (green) form a **bipartite subgraph** — the maximum cut! ✅

---

## 🔬 Worked Examples

---

### Example 1: Triangle 🔺

A 3-cycle with weights $5, 10, 3$.

<pre>
graph LR
    0((0)) -- "5" --- 1((1))
    1 -- "10" --- 2((2))
    2 -- "3" --- 0
    style 0 fill:#bbdefb,stroke:#1565c0
    style 1 fill:#bbdefb,stroke:#1565c0
    style 2 fill:#bbdefb,stroke:#1565c0
    linkStyle 0 stroke:#1565c0,stroke-width:2px
    linkStyle 1 stroke:#1565c0,stroke-width:2px
    linkStyle 2 stroke:#1565c0,stroke-width:2px
</pre>

]

**Faces:** Inner $(0,1,2)$, Outer $(0,2,1)$ — **both odd** (3 edges each)

**Dual:** 2 vertices connected by 3 parallel edges (weights 5, 10, 3)

**Shortest paths:** $d = 3$ (the minimum weight edge)

**MWPM:** Pair the two odd faces via weight-3 path

**Excluded:** The weight-3 edge $(2, 0)$

**Max cut:** $\{(0,1), (1,2)\}$ with **total weight = 15** ✅

---

### Example 2: Square + Diagonal 🔷

Square 1-2-3-4 (weights 5,10,5,10) + diagonal 1-3 (weight 2).

<pre>
graph LR
    1((1)) -- "5" --- 2((2))
    2 -- "10" --- 3((3))
    3 -- "5" --- 4((4))
    4 -- "10" --- 1
    1 -- "2" --- 3
    style 1 fill:#bbdefb,stroke:#1565c0
    style 2 fill:#fce4ec,stroke:#c62828
    style 3 fill:#e3f2fd,stroke:#1565c0
    style 4 fill:#fce4ec,stroke:#c62828
    linkStyle 0 stroke:#1565c0,stroke-width:2px
    linkStyle 1 stroke:#1565c0,stroke-width:2px
    linkStyle 2 stroke:#1565c0,stroke-width:2px
    linkStyle 3 stroke:#1565c0,stroke-width:2px
    linkStyle 4 stroke:#ff9800,stroke-width:3px
</pre>

]

**Faces:** $(1,2,3)$ (odd), $(1,3,4)$ (odd), $(1,4,3,2)$ (even)

**Dual:** 3 vertices forming a triangle with weights 10, 5, 2

**MWPM:** Pair the two odd faces with shortest distance = 2 (via diagonal)

**Excluded:** The diagonal edge $(1,3)$

**Max cut:** All 4 outer edges — **total weight = 30** ✅

---

## ⚡ Biconnected Component (BC) Speedup

---

### The Bottleneck 😓

**Problem:** All-pairs shortest paths on the full dual graph is $O(|V_{\text{dual}}|^3)$.

For large circuits with thousands of faces, this becomes **prohibitively expensive**.

**Key Observation:**

MAX-CUT is **additive** over biconnected components (blocks)!

- Biconnected components share only **articulation points** (vertices), **never edges**
- No cycle can span two different blocks
- The optimal cut is the **disjoint union** of each block's optimal cut

---

### BC Decomposition 🔧

Decompose the graph into blocks, solve each independently, union the results.

<pre>
graph TD
    subgraph Full["Full Graph"]
        0((0)) --- 1((1))
        1 --- 2((2))
        2 --- 0
        2 --- 3((3))
        3 --- 4((4))
        4 --- 2
    end
    subgraph BC2["BC Component 2"]
        D((2)) --- E((3))
        E --- F((4))
        F --- D
    end
    subgraph BC1["BC Component 1"]
        A((0)) --- B((1))
        B --- C((2))
        C --- A
    end
    style Full fill:#e3f2fd
    style BC1 fill:#e8f5e9
    style BC2 fill:#fce4ec
    style 0 fill:#bbdefb,stroke:#1565c0
    style 1 fill:#bbdefb,stroke:#1565c0
    style 2 fill:#ffcc80,stroke:#e65100,stroke-width:3px
    style 3 fill:#bbdefb,stroke:#1565c0
    style 4 fill:#bbdefb,stroke:#1565c0
    style A fill:#bbdefb,stroke:#1565c0
    style B fill:#bbdefb,stroke:#1565c0
    style C fill:#ffcc80,stroke:#e65100,stroke-width:3px
    style D fill:#ffcc80,stroke:#e65100,stroke-width:3px
    style E fill:#bbdefb,stroke:#1565c0
    style F fill:#bbdefb,stroke:#1565c0
</pre>

]

> Node 2 (orange) is the **articulation point** — shared between both blocks.

---

### Why This Works 🧠

**Theorem:** MAX-CUT on a planar graph = disjoint union of MAX-CUT on each biconnected component.

**Proof sketch:**
- Biconnected components share only articulation points (vertices)
- No cycle exists across two components
- The cut's bipartition is trivially consistent at articulation points (they can be assigned arbitrarily to $S$ or $V \setminus S$ in each component independently)
- The edge set is partitioned among components

.font-sm.mb-xs[

```python
def solve_hadlock_max_cut(G, weight="weight"):
    is_planar, _ = nx.check_planarity(G)
    if not is_planar:
        raise nx.NetworkXException(...)

components = _biconnected_components(G)
    cut_edges = set()
    for comp in components:
        comp_cut = _solve_hadlock_component(comp, weight)
        cut_edges.update(comp_cut)
    return cut_edges
```
]

---

### Speedup Analysis 📈

| Step | Before (single dual) | After (per block) | Win |
| - | - | - | - |
| **All-pairs SP** | $O(V_{\text{dual}}^3)$ | $\sum O(V_i^3)$ | **~$4\times$** |
| **MWPM** | $O(k^3)$ | $\sum O(k_i^3)$ | **~$4\times$** |
| **Face finding** | $O(F)$ | $\sum O(F_i)$ | Same |

**Example:** Graph split into 2 equal blocks:

$$ \left(\frac{n}{2}\right)^3 + \left(\frac{n}{2}\right)^3 = \frac{n^3}{4} $$

That's a **$4\times$ speedup** on the dominant terms! For more components, savings grow. 🚀

---

### BC Algorithm: Tarjan's DFS 🧬

```cpp
template <typename Graph>
auto biconnected_components(const Graph& G) {
    // DFS tracking discovery time (disc) and low-link values
    // When low[v] >= disc[u], u is an articulation point
    // Pop edges from stack → one biconnected component

// Root: articulation if children > 1
    // Non-root: articulation if low[v] >= disc[u]
}
```

The algorithm uses **Tarjan's bridge-finding** technique adapted to collect node-sets for each block. Articulation points appear in multiple components (shared), but edges belong to exactly one component.

---

### 🧵 Thread Pool Parallelization

BC components are independent (disjoint edges) — solve them **in parallel** with a thread pool. ⚡

```cpp
netlistx::thread_pool pool;  // worker pool
std::vector<std::future<py::set<edge_t>>> futures;

for (size_t i = 0; i < n_comps; ++i) {
    futures.push_back(pool.enqueue([&, i]() {
        return solve_hadlock_component(
            comp_g, weight, faces);
    }));
}

py::set<edge_t> cut_edges;
for (auto& f : futures) {
    auto comp_cut = f.get();
    cut_edges.insert(comp_cut.begin(),
                     comp_cut.end());
}
```
]
]
.pull-right[
.mermaid[

<pre>
graph TD
    BC["BC Components"] --> Pool
    subgraph Pool["Thread Pool (hardware_concurrency workers)"]
        W1["Worker 1"]
        W2["Worker 2"]
        W3["Worker ⋯"]
    end
    W1 -. "Comp 0" .-> R["Union of Cuts"]
    W2 -. "Comp 1" .-> R
    W3 -. "Comp N" .-> R
    R --> MC["MAX-CUT 🎉"]
    style BC fill:#e3f2fd
    style Pool fill:#fce4ec,stroke:#c62828
    style W1 fill:#ffcdd2,stroke:#c62828
    style W2 fill:#ffcdd2,stroke:#c62828
    style W3 fill:#ffcdd2,stroke:#c62828
    style R fill:#f3e5f5,stroke:#7b1fa2
    style MC fill:#e8f5e9,stroke:#2e7d32,stroke-width:3px
</pre>

]
]

Same paradigm also accelerates **randomized vertex cover** (`rand_vertex_cover_mt`) in the `netlistx-cpp` package. 🔄

---

## 💻 Implementation Highlights

---

### Python Implementation 🐍

The `netlistx` package implements the bc-optimized Hadlock algorithm:

```python
# src/netlistx/hadlock.py

def _biconnected_components(G):
    """Decompose into bc components for MAX-CUT speedup."""
    return [G.subgraph(comp).copy()
            for comp in nx.biconnected_components(G)]

def _solve_hadlock_component(G, weight):
    """Core Hadlock: embedding → dual → odd faces → SP → MWPM."""
    _, embedding = nx.check_planarity(G)
    faces = _find_faces(embedding)
    du_G = _build_dual(G, faces, weight)
    odd_faces = [i for i, f in enumerate(faces) if len(f) % 2 == 1]
    # ... all-pairs shortest paths, complete graph, MWPM, exclude
    return all_edges - excluded
```

---

### C++ Implementation ⚡

The `netlistx-cpp` package provides a template-based C++20 version:

.font-sm.mb-xs[

```cpp
// include/netlistx/hadlock.hpp (C++20)

namespace netlistx::detail {

template <typename Graph>
auto biconnected_components(const Graph& G)
    -> std::vector<py::set<typename Graph::node_t>>;

template <typename Graph, typename WeightFunc>
auto solve_hadlock_component(
    const Graph& G, WeightFunc weight,
    const std::vector<std::vector<node_t>>& faces
) -> py::set<std::pair<node_t, node_t>>;

} // namespace netlistx::detail
```
]

**Key features:**
- Coroutine-based `Generator<T>` for lazy iteration
- Dijkstra with `std::priority_queue` for shortest paths
- Exact MWPM via DP ($n \leq 18$) or greedy 2-approximation ($n > 18$)
- Thread pool parallelization of BC components 🧵⚡
- Built with **xmake** (not CMake) for the C++ project

---

### MWPM: Exact vs Greedy 🎯

| Approach | Complexity | When to Use |
| -------- | ---------- | ----------- |
| **Exact DP** $O(2^k \cdot k^2)$ | $k \leq 18$ | Small odd-face sets (most blocks!) |
| **Greedy** $O(k^2 \log k)$ | $k > 18$ | Large odd-face sets |

```cpp
template <typename Node>
auto min_weight_perfect_matching(
    const std::vector<int>& odd_faces,
    const std::vector<std::vector<int>>& dist
) {
    const int n = odd_faces.size();
    if (n <= 18) return exact_mwpm<Node>(odd_faces, dist);
    return greedy_mwpm<Node>(odd_faces, dist);
}
```

> After BC decomposition, most blocks have $k \leq 18$ odd faces, enabling exact DP! 🔥

---

## 📊 Complexity Analysis

---

### Full Algorithm Complexity 📐

.font-sm.mb-xs[

| Step | Complexity | Notes |
| ---- | ---------- | ----- |
| Planarity check | $O(n)$ | Linear-time for planar graphs |
| Face finding | $O(n)$ | Walk half-edges |
| Dual construction | $O(m)$ | $m$ = primal edges |
| **All-pairs SP** 🟡 | $\sum O(V_i^3)$ | Per bc component |
| **MWPM** 🟡 | $\sum O(k_i^3)$ or $O(2^{k_i} \cdot k_i^2)$ | Per bc component |
| Cut recovery | $O(m)$ | Linear scan of edges |

]

**Without BC:** $O(V^3 + k^3)$ where $V$ = dual size, $k$ = odd faces

**With BC:** $\sum O(V_i^3 + k_i^3) \ll O(V^3 + k^3)$

> The smaller each component, the **more dramatic** the savings! 📉

---

### When to Use BC Decomposition 🎯

.mermaid[
<pre>
graph LR
    A("Input Graph") --> B{"Planar?"}
    B -->|"Yes"| D{"Many BC\nComponents?"}
    D -->|"No"| E("Solve Directly")
    D -->|"Yes"| F("BC Decompose + \nSolve per Block")
    B -->|"No"| C("Raise Error")
    style A fill:#e3f2fd
    style B fill:#fff9c4
    style C fill:#fce4ec
    style D fill:#fff9c4
    style E fill:#e8f5e9
    style F fill:#e8f5e9
</pre>
]

**✅ Good for BC:**
- Large graphs (1000+ nodes)
- Many articulation points
- Circuit netlists (sparse)
- Hierarchical designs

]
.pull-right[

**❌ No benefit (skip BC):**
- Single biconnected component
- Very small graphs (< 50 nodes)
- Dense planar graphs
- Triangulated meshes

]

---

## 🏁 Key Takeaways

---

### Summary 📝

#### 🧩 Hadlock's Algorithm

- Reduces planar MAX-CUT to MWPM 🎯
- Uses dual graph + odd faces 🔗
- Polynomial time for planar graphs ✅
- Excludes minimum-weight edges breaking odd faces

]

#### ⚡ BC Optimization

- MAX-CUT is additive over blocks ➕
- Dramatically smaller subproblems 📉
- Enables exact MWPM via DP 🔥
- **4×+ speedup** on realistic circuits 🚀

]

**Resources:**

- 📖 Python: `netlistx` (github.com/luk036/netlistx)
- ⚡ C++: `netlistx-cpp` (github.com/luk036/netlistx-cpp)
- 📄 Hadlock (1975), *SIAM Journal on Computing*, 4(3), 221-225

<pre>
graph LR
    A("Planar\nGraph") --> B("Biconnected\nComponents")
    B --> C("Per-Component\nHadlock")
    C --> D("Union of\nCuts")
    D --> E("MAX-CUT 🎉")
    style A fill:#e3f2fd
    style B fill:#fff9c4
    style C fill:#e8f5e9
    style D fill:#f3e5f5
    style E fill:#e8f5e9,stroke:#2e7d32,stroke-width:3px
</pre>

]

---

## 🙋 Q&A

**Hadlock's Algorithm for Planar MAX-CUT**

*Questions?* 🎤

---

# 👋 Thank You!

## Happy Coding! 💻 🚀