layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # 🔪 MAX-k-CUT Problem: Foundations and Applications @luk036 👨‍💻 · 2026 📅 --- ### 📝 Abstract The MAX-k-CUT problem is a fundamental graph partitioning challenge in computational optimization. It involves dividing graph vertices into k distinct color groups to maximize the weight of edges connecting differently colored vertices. This lecture explores the mathematical foundations, computational complexity, solution approaches, and practical applications of the MAX-k-CUT problem, with special focus on planar graph techniques and divide-and-conquer methods using SPQR-trees. --- ### 🧩 MAX-${\color{coral}k}$-CUT Problem - Also known as MINIMUM EDGE DELETION ${\color{coral}k}$-PARTITION (Garey and Johnson GT32) 🔹 - INSTANCE: Graph $G=({\color{salmon}V}, {\color{lime}E})$ and a weight function ${\color{coral}w}: {\color{lime}E} \rightarrow \mathbb{N}$ 🔹 - SOLUTION: An ${\color{coral}k}$-partition, i.e., a color assignment ${\color{coral}c}: {\color{salmon}V} \rightarrow \{1,2,...,{\color{coral}k}\}$ 🔹 - MEASURE: The sum of weights of edges with different colors. 🔹 - Bad News: APX-hard (meaning it cannot be approximated arbitrarily well in polynomial time unless P=NP). 😟 --- ### ✂️ MAX-CUT Problem (${\color{coral}k}$ = 2) - Approximable within 1.1383 (using Semidefinite Relaxation) \[Goemans and Williamson 93\]. ✅ - Not approximable within 1.058 \[Hastad 97\]. ❌ - Polynomial time solvable for planar graphs, since the problem is equivalent to the T-join problem in the dual graph \[Hadlock75\]. 🏞️ - Approximable within 9/4 for planar graphs (using primal-dual method) \[Goemans and Williamson 95\]. 🔄 - Linear time solvable for bipartite graphs due to natural 2-coloring properties of bipartite graphs. ⚖️ - Linear time solvable for series-parallel graphs (using SPQR-tree decomposition techniques). 🧩 --- ### ✂️ MAX-CUT Graph Partitioning .mermaid[ <pre> graph LR subgraph "Partition A" A((v1)) B((v2)) end subgraph "Partition B" C((v3)) D((v4)) end A === C A === D B === D style A fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style B fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style C fill:#fff3e0,stroke:#e65100,stroke-width:3px style D fill:#ffcdd2,stroke:#c62828,stroke-width:3px </pre> ] --- ### 🌍 Real-World Applications - Multiple Patterning Lithography 🎨 In semiconductor manufacturing, MAX-k-CUT helps resolve conflicts in layout decomposition for advanced lithography processes. - Network Design & Resource Allocation 🌐 Optimizes network partitioning and resource distribution in telecommunications and computing systems. - Image Segmentation 🖼️ Partitions images into meaningful regions for computer vision applications and medical imaging analysis. - Many Others 🔍 e.g. Via minimization in Mutli-Chip Module (MCM) --- ### 🔍 Overview of Planar Graph Approach (Hadlock's algorithm) 1. Decompose $G$ into its bi-connected components. 🔨 2. For each biconnected component in $G'$, 1. Approximate $G'$ by a planar graph $P$ 🔄 2. construct a planar embedding 🏗️ 3. construct a dual graph ${\color{blue}P^*}$ 🔄 4. construct a complete graph $C({\color{salmon}V}, {\color{lime}E})$, where 🧩 - ${\color{salmon}V}$ is a set of odd-degree vertices in ${\color{blue}P^*}$ - the weight of each edge is the shortest path of two vertices 5. find the **minimum perfect matching** solution. 🔍 The matching edges are the conflict edges that have to be deleted. 3. Reinsert the non-conflicting edges from $G$. 🔙 --- ### 🔍 Hadlock's Algorithm - Decompose into Components 🪓 Break the original graph G into its bi-connected components G' using linear time algorithms (available in LEDA package) - Approximate to Planar Graph 🏞️ Convert each compoment G' to a planar graph P (NP-hard, typically using greedy algorithms in O(n²) time) - Process Each Component 🔄 For each component P: construct planar embedding, build dual graph P*, create complete graph of odd-degree vertices - Find Minimum Perfect Matching 🤝 Identify conflict edges that must be deleted, then reinsert non-conflicting edges from G --- ### 🏞️ Planar Graph Approach - Step 1: Decompose $G$ into its bi-connected components in linear time (available in the LEDA package).  --- ### 🏞️ Planar Graph Approach .pull-left[ - Step 2: Approximate $G'$ with a planar graph $P$ - It is NP-hard. - The naive greedy algorithm takes $O({\color{coral}n}^2)$ time. - Any good suggestion? ] .pull-right[  ] --- ### 🏞️ Planar Graph Approach - Step 3: For each component $P$, construct a planar embedding in linear time  👉 Note: planar embedding may not be unique unless $P$ is tri-connected. --- ### 🏞️ Planar Graph Approach .pull-left[ - Step 4: For each component P, construct its dual graph ${\color{blue}P^*}$ in linear time. ] .pull-right[  ] --- ### 🏞️ Planar Graph Approach .pull-left[ - Step 5: Find the minimum weight perfect matching of ${\color{blue}P^*}$. - Polynomial time solvable. - Can be formulated as a network flow problem. 👉 Note: complete graph vs. Voronoi graph ] .pull-right[  ] --- ### 🏞️ Planar Graph Approach .pull-left[ - Step 6: reinsert the non-conflicting edges in $G$. 👉 Note: practically we keep track of conflicting edges. ] .pull-right[  ] --- class: nord-light, middle, center ## SPQR-Tree 🌳 --- ### 🔗 Connected Graph - Recall that a graph $G = ({\color{salmon}V}, {\color{lime}E})$ is a *connected* if every pair of vertices ${\color{salmon}u}, {\color{salmon}v}$ in $G$ is connected by a path. - A graph can be divided into its connected components in linear time. - Clearly, the color assignment problem can be solved independently for each connected component without affecting any QoR. --- ### 🔗 Bi-connected Graph - A vertex is called a *cut-vertex* of a connected graph $G$ if removing it disconnects $G$. - If no cut-vertex is found in $G$, then the graph is called a bi-connected graph. - In the following example, ${\color{salmon}a}$, ${\color{salmon}b}$ and ${\color{salmon}c}$ are cut-vertices.  --- ### 🔗 Bi-connected Components $G'$ - A division of $G$ into its bi-connected components can be performed in linear time by using a simple depth-first search to identify cut-vertices. - It can be easily shown that the color assignment problem can be solved for each bi-connected component separately without affecting any QoR [@chiang_fast_2005] - Question: Is it possible to further decompose the graph? ❓ --- ### 🔗 Tri-connected Graph - If removing a pair of vertices will disconnect $G'$, the pair is called a *separation pair* of $G'$. - If no separation pair can be found in $G'$, then it is called a *tri-connected graph*. - In the following example, $({\color{salmon}a},{\color{salmon}b})$, $({\color{salmon}g},{\color{salmon}h})$, $({\color{salmon}c},{\color{salmon}d})$, $({\color{salmon}c},{\color{salmon}e})$ and $({\color{salmon}c},{\color{salmon}f})$ are separation pairs.  --- ### 🏗️ Tri-connected Graph Division  --- ### 🌳 SPQR-tree  - A division of $G'$ into its tri-connected components can be performed by identifying the separation pairs in linear time with the help of SPQR-tree [@gutwenger_linear_2001]. --- ### 🌳 SPQR-Tree Decomposition Each node in the tree represents a skeleton (a simplified version of a component) classified into one of four types: - Series (S) 🔄 Skeleton is a cycle graph, representing a chain of components connected in series - Parallel (P) ⏸️ Skeleton contains two vertices with multiple (≥3) parallel edges between them - Trivial (Q) 🔘 Skeleton has two vertices with one real edge and one virtual edge - Rigid (R) 🏗️ Skeleton is a tri-connected graph not falling into the above categories --- class: nord-light, middle, center ## Divide-and-Conquer Method 🪓 --- ### 🪓 Divide-and-Conquer Method - Divide 🔪 Decompose the conflict graph into its tri-connected components using SPQR-tree. This creates a hierarchical structure of simpler subproblems. - Conquer 🏆 Solve each tri-connected component in a bottom-up manner, calculating two possible solutions: separation vertices (s,t) of the same color and (s,t) of opposite colors. - Combine 🧩 Merge the solutions in a top-down manner to construct a complete solution for the original graph, selecting optimal configurations at each step. This approach efficiently handles different skeleton types (S, P, R) with specific strategies for each. The bottom-up phase computes optimal solutions for components, while the top-down phase ensures global consistency. ---  --- ### 🔄 S Type  --- ### ⏸️ P Type  --- ### 🏗️ R Type  --- ### 🔝 Top-down Merging  --- ### 🏭 Application to Double Patterning .pull-left[  ] .pull-right[  ] Unlike conventional optical lithography, which exposes the photoresist once under one mask, masks is exposed twice by splitting them into two, each with half its feature density. --- ### 🔬 45 nm SDFFRS_X2 Layer 11, 9   --- ### 🔍 45 nm Example  ---  : fft_all, 320K polygons --- ### 📊 Experimental Results | \#poly | \#nodes/\#edges | w/ spqr | w/o spqr | time | cost | | ------ | --------------- | ------- | -------- | ----- | ----- | | 3631 | 31371/52060 | 13.29 | 38.25 | 65.3% | 4.58% | | 9628 | 83733/138738 | 199.94 | 2706.12 | 92.6% | 2.19% | | 18360 | 159691/265370 | 400.43 | 4635.14 | 91.4% | 1.18% | | 31261 | 284957/477273 | 1914.54 | 9964.18 | 80.7% | 1.61% | | 49833 | 438868/738759 | 3397.26 | 15300.9 | 77.8% | 1.76% | | 75620 | 627423/1057794 | 3686.07 | 17643.9 | 79.1% | 2.50% | : Experimental results of the runtime and cost reduction (with minimizing the number of stitches) --- ### 🚧 Challenges for k≥3 For k≥3, the MAX-k-CUT problem becomes significantly more challenging. It's not approximable within O($|{\color{lime}E}|$) and remains NP-hard even for tri-partite graphs with k=3. Current approaches rely on heuristic algorithms such as using "pairwise coloring" techniques. --- ### 🔮 Future Directions - Advanced Approximation 🎯 Developing better approximation algorithms for specific graph classes - Hardware Acceleration ⚡ Leveraging specialized hardware for graph algorithms - Machine Learning Integration 🤖 Using ML to guide heuristic choices in complex instances Future research directions include developing specialized algorithms for industry-specific graph structures, exploring quantum computing approaches for combinatorial optimization, and creating hybrid methods that combine theoretical guarantees with practical performance. --- count: false class: nord-dark, middle, center .pull-left[ ## Q&A 🎤 ] .pull-right[  ]