Packing multiway cuts in capacitated graphs

ABSTRACT

We consider the following "multiway cut packing" problem in undirected graphs: 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₁, ..., 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 containing 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 the goal, informally stated, 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² 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 LP-rounding-based algorithm guarantees a maximum edge load of at most 8OPT + 4 in general graphs. Our approach is based on the observation that every instance of the problem admits a laminar solution (that is, no pair of cuts in the solution crosses) that is near-optimal.

REFERENCES

• 1: Siddharth Barman , Shuchi Chawla, Packing multiway cuts in capacitated graphs, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1048-1057, January 04-06, 2009, New York, New York
• 2: Gruia Călinescu , Howard Karloff , Yuval Rabani, An improved approximation algorithm for MULTIWAY CUT, Journal of Computer and System Sciences, v.60 n.3, p.564-574, June 2000 [doi>10.1006/jcss.1999.1687]
• 3: Gruia Calinescu , Howard Karloff , Yuval Rabani, Approximation Algorithms for the 0-Extension Problem, SIAM Journal on Computing, v.34 n.2, p.358-372, 2005 [doi>10.1137/S0097539701395978]
• 4: C. Chekuri , S. Khanna , J. Naor , L. Zosin, A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem, SIAM Journal on Discrete Mathematics, v.18 n.3, p.608-625, 2005 [doi>10.1137/S0895480101396937]
• 5: Alexander V. Karzanov, Minimum 0-extensions of graph metrics, European Journal of Combinatorics, v.19 n.1, p.71-101, Jan., 1998 [doi>10.1006/eujc.1997.0154]
• 6: Jon Kleinberg , Éva Tardos, Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields, Journal of the ACM (JACM), v.49 n.5, p.616-639, September 2002 [doi>10.1145/585265.585268]
• 7: Ming Li , Bin Ma , Lusheng Wang, On the closest string and substring problems, Journal of the ACM (JACM), v.49 n.2, p.157-171, March 2002 [doi>10.1145/506147.506150]
• 8: Yuval Rabani , Leonard J. Schulman , Chaitanya Swamy, Approximation algorithms for labeling hierarchical taxonomies, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.671-680, January 20-22, 2008, San Francisco, California
• 9: R. Ravi , John D. Kececioglu, Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree, Discrete Applied Mathematics, v.88 n.1-3, p.355-366, Nov. 9, 1998 [doi>10.1016/S0166-218X(98)00079-1]
• 10: Lusheng Wang , Dan Gusfield, Improved approximation algorithms for tree alignment, Journal of Algorithms, v.25 n.2, p.255-273, Nov. 1997 [doi>10.1006/jagm.1997.0882]
• 11: Lusheng Wang , Tao Jiang , Dan Gusfield, A More Efficient Approximation Scheme for Tree Alignment, SIAM Journal on Computing, v.30 n.1, p.283-299, 2000 [doi>10.1137/S0097539796313507]
• 12: L. Wang, T. Jiang, and E. Lawler. Approximation algorithms for tree alignment with a given phylogeny. Algorithmica, 16(3):302--315, 1996.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms