In Directed Multiway Cut(Dir-MC) the input is an edge-weighted directed graph @math and a set of @math terminal nodes @math ; the goal is to find a min-weight subset of edges whose removal ensures that there is no path from @math to @math for any @math . In Node-weighted Multiway Cut(Node-MC) the input is a node-weighted undirected graph @math and a set of @math terminal nodes @math ; the goal is to remove a min-weight subset of nodes to disconnect each pair of terminals. Dir-MC admits a @math -approximation [Naor, Zosin '97] and Node-MC admits a @math -approximation [Garg, Vazirani, Yannakakis '94], both via rounding of LP relaxations. Previous rounding algorithms for these problems, from nearly twenty years ago, are based on careful rounding of an "optimum" solution to an LP relaxation. This is particularly true for Dir-MC for which the rounding relies on a custom LP formulation instead of the natural distance based LP relaxation [Naor, Zosin '97]. In this paper we describe extremely simple and near linear-time rounding algorithms for Dir-MC and Node-MC via a natural distance based LP relaxation. The dual of this relaxation is a special case of the maximum multicommodity flow problem. Our algorithms achieve the same bounds as before but have the significant advantage in that they can work with "any feasible" solution to the relaxation. Consequently, in addition to obtaining "book" proofs of LP rounding for these two basic problems, we also obtain significantly faster approximation algorithms by taking advantage of known algorithms for computing near-optimal solutions for maximum multicommodity flow problems. We also investigate lower bounds for Dir-MC when @math and in particular prove that the integrality gap of the LP relaxation is @math even in directed planar graphs.
@cite_5: Given a system (V,T,f,k), where V is a finite set, Open image in new window is a submodular function and k≥2 is an integer, the general multiway partition problem (MPP) asks to find a k-partition Open image in new window = V1,V2,...,V k of V that satisfies Open image in new window for all i and minimizes f(V1)+f(V2)+···+f(V k ), where Open image in new window is a k-partition of Open image in new window hold. MPP formulation captures a generalization in submodular systems of many NP-hard problems such as k-way cut, multiterminal cut, target split and their generalizations in hypergraphs. This paper presents a simple and unified framework for developing and analyzing approximation algorithms for various MPPs.
@cite_27: 
@cite_13: We study the approximability of multiway partitioning problems, examples of which include Multiway Cut, Node-weighted Multiway Cut, and Hypergraph Multiway Cut. We investigate these problems from the point of view of two possible generalizations: as Min-CSPs, and as Submodular Multiway Partition problems. These two generalizations lead to two natural relaxations that we call respectively the Local Distribution LP, and the Lovasz relaxation. The Local Distribution LP is generally stronger than the Lovasz relaxation, but applicable only to Min-CSP with predicates of constant size. The relaxations coincide in some cases such as Multiway Cut where they are both equivalent to the CKR relaxation. We show that the Lovasz relaxation gives a (2--2 k)-approximation for Submodular Multiway Partition with k terminals, improving a recent 2-approximation [2]. We prove that this factor is optimal in two senses: (1) A (2--2 k -- e)-approximation for Submodular Multiway Partition with k terminals would require exponentially many value queries (in the oracle model), or imply NP = RP (for certain explicit submodular functions). (2) For Hypergraph Multiway Cut and Node-weighted Multiway Cut with k terminals, both special cases of Submodular Multiway Partition, we prove that a (2--2 k -- e)-approximation is NP-hard, assuming the Unique Games Conjecture. Both our hardness results are more general: (1) We show that the notion of symmetry gap, previously used for submodular maximization problems [19, 6], also implies hardness results for submodular minimization problems. (2) Assuming the Unique Games Conjecture, we show that the Local Distribution LP gives an optimal approximation for every Min-CSP that includes the Not-Equal predicate. Finally, we connect the two hardness techniques by proving that the integrality gap of the Local Distribution LP coincides with the symmetry gap of the multilinear relaxation (for a related instance). This shows that the appearance of the same hardness threshold for a Min-CSP and the related submodular minimization problem is not a coincidence.
The CKR-relaxation makes use of the observation that can be viewed as a partition problem where the goal is to partition the node set @math into @math parts @math to minimize @math subject to the constraint that for @math , @math . Submodular Multiway Partition ( ) is a generalization from the setting of graphs to arbitrary submodular functions. Here we are given a non-negative submodular function @math over the ground set @math along with terminals @math . The goal is to partition @math into @math to minimize @math subject to the constraint that @math for @math . If @math is symmetric, as in the case of the undirected graph cut function, we obtain the Symmetric Submodular Multiway Partition ( ) problem. These problems were considered by Zhao, Nagamochi and Ibaraki @cite_5 who analyzed greedy-splitting algorithms, and more recently by Chekuri and Ene @cite_27 who used a Lov 'asz-extension based convex relaxation. Interestingly, the convex relaxation when specialized to yields the CKR-relaxation.Chekuri and Ene @cite_27 obtained a @math -approximation for and @math -approximation for . Ene, Vondr 'ak and Wu @cite_13 improved the bound for to @math and also obtained lower bound results in the oracle model.