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-$k$-CUT Problem 🧩 - Also known as MINIMUM EDGE DELETION $k$-PARTITION (Garey and Johnson GT32) 🔹 - INSTANCE: Graph $G=({\color{salmon}V}, {\color{lime}E})$ and a weight function $w: {\color{lime}E} \rightarrow \mathbb{N}$ 🔹 - SOLUTION: An $k$-partition, i.e., a color assignment $c: {\color{salmon}V} \rightarrow \{1,2,...,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 ($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:#2196f3 style B fill:#4caf50 style C fill:#ff9800 style D fill:#f44336 </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(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: 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 $u, 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, $a$, $b$ and $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, $(a,b)$, $(g,h)$, $(c,d)$, $(c,e)$ and $(c,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: 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[  ]