A 2-Approximation Algorithm for the Directed Multiway Cut Problem

A directed multiway cut separates a set of terminals s/sub 1/, .. ., s/sub /spl kappa// in a directed capacitated graph G=(V, E). Finding a minimum capacity directed multiway cut is an NP-complete problem. We give a polynomial-time algorithm that achieves an approximation factor of 2 for this problem. This improves the result of Garg, Vazirani and Yannakakis (1994) who gave an algorithm that achieves an approximation factor of 2 log /spl kappa/. Our approximation algorithm uses a novel technique for relaxing a multiway flow function in order to find a directed multiway cut. It also implies that the integrality gap of the linear program for the directed multiway cut problem is at most 2.

Authors

• Joseph Naor
• Leonid Zosin

Keywords

• Approximation algorithms
• Computer science
• Polynomials
• Marine vehicles
• NP-complete problem
• Algorithm design and analysis
• Ear
• Cut Problem
• 2-approximation Algorithm
• Objective Function
• Optimal Function
• Estimation Algorithm
• Linear Programming
• First Approximation
• Directed Graph
• Pathfinding
• Flow Path
• Flow Values
• Amount Of Flow
• Optimal Flow
• Version Of Problem
• Minimum Capacity
• Idea Of The Proof
• Optimal Cut
• Commodity Flows
• Sum Of Flows
• Terminal Pair
• Complementary Slackness
• Congestion Pricing
• Undirected