Approximating Directed Multicuts

The seminal paper of F. T. Leighton and S. Rao (1988) and subsequent papers presented approximate min-max theorems relating multicommodity flow values and cut capacities in undirected networks, developed the divide-and-conquer method for designing approximation algorithms, and generated novel tools for utilizing linear programming relaxations. Yet, despite persistent research efforts, these achievements could not be extended to directed networks, excluding a few cases that are "symmetric" and therefore similar to undirected networks. The paper is an attempt to remedy the situation. We consider the problem of finding a minimum multicut in a directed multicommodity flow network, and give the first nontrivial upper bounds on the maxflow-to-min multicut ratio. Our results are algorithmic, demonstrating nontrivial approximation guarantees.

Authors

• Joseph Cheriyan
• Howard J. Karloff
• Yuval Rabani

Keywords

• Approximation algorithms
• Computer science
• Contracts
• Statistics
• Combinatorial mathematics
• Design methodology
• Algorithm design and analysis
• Linear programming
• Upper bound
• Chromium
• Estimation Algorithm
• Flow Values
• Undirected Network
• Divide-and-conquer Approach
• Linear Programming Relaxation
• Directed Graph
• Maximum Flow
• Universal Constant
• Minimum Capacity
• Subset Of Vertices
• Infinite Capacity