  We consider the following "multiway cut packing" problem in undirected
graphs: we are given a graph G=(V,E) and k commodities, each corresponding to a
set of terminals located at different vertices in the graph; our goal is to
produce a collection of cuts {E_1,...,E_k} such that E_i is a multiway cut for
commodity i and the maximum load on any edge is minimized. The load on an edge
is defined to be the number of cuts in the solution crossing the edge. In the
capacitated version of the problem the goal is to minimize the maximum relative
load on any edge--the ratio of the edge's load to its capacity. Multiway cut
packing arises in the context of graph labeling problems where we are given a
partial labeling of a set of items and a neighborhood structure over them, and,
informally, the goal is to complete the labeling in the most consistent way.
This problem was introduced by Rabani, Schulman, and Swamy (SODA'08), who
developed an O(log n/log log n) approximation for it in general graphs, as well
as an improved O(log^2 k) approximation in trees. Here n is the number of nodes
in the graph. We present the first constant factor approximation for this
problem in arbitrary undirected graphs. Our approach is based on the
observation that every instance of the problem admits a near-optimal laminar
solution (that is, one in which no pair of cuts cross each other).
