| CSC5160: Combinatorial Optimization and Approximation Algorithms Topic: Graph Partitioning Problems Date: 14/03/2008 (2009) | |||||||||||||||
Abstract | |||||||||||||||
| This lecture gives a general introduction of graph partitioning problems. We will begin with the definitions of some classic graph partitioning problems (e.g. multiway cut, multicut, sparsest cut), and discuss their relationships. Then we will focus on deriving two approximation algorithms. For the multiway cut problem, we will show a 2-approximation algorithm through a combinatorial argument. For the multicut problem, we will present an O(log k)-approximation algorithm using an LP-based approach, where k is the number of source-sink pairs (commodities). 18.1 Graph Partitioning Problems Consider a graph G(V, E), where V denotes the set of vertices and E the set of edges. The generic graph partition problem is: Given G and an integer k> 1 and a weight function on edges, partition V into k parts (subsets) V1, V2,...Vk such that the parts are disjoint and satisfy some cut requirements, and the total cost of edges with endpoints in different parts is minimized. Different problems arise depending on the different cut requirements. Some well-studied problems are mentioned below. 18.1.1 Minimum s − t Cut Given a connected, undirected graph G = (V, E) with a weight function on edges, w: E → R +, a cut is defined by a partition of V into two sets, say V ′ and V − V ′ , and consists of all edges that have one endpoint in each partition. Given terminals s, t ∈ V, consider a partition of V that separates s and t. The cut defined by such a partition will be called an s − t cut. The problems of finding a minimum weight cut and a minimum weight s − t cut can be efficiently solved using flow techniques as in Lecture 6 and 7. 18.1.2 Multiway Cut Given a set of terminals S = {s1, s2,..., sk} ⊆ V, a multiway cut is a set of edges whose removal disconnects the terminals from each other. The multiway cut problem asks for the minimum weight multiway cut, as shown on the left in Figure 18.1.1(a). 18.1.3 Multicut Given k source-sink pairs {(s1, t1), (s2, t2),..., (sk, tk)}, a multicut is a set of edges whose removal disconnects each source-sink pair. The multicut problem asks for the minimum weight multicut. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||