Packing Cuts in Graphs

We address the problem of finding the largest collection of edge-disjoint cuts in an undirected graph, dubbed CUT PACKING, focusing on its complexity, about which very little is known. We show a very close relationship with INDEPENDENT SET, namely, for the same graph G, the size of the largest cut packing of G is at least the independence number of G, and at most twice that number. This implies that any approximation guarantee for INDEPENDENT SET immediately extends to CUT PACKING within a factor of 2. In particular, this yields a 2-approximation algorithm for CUT PACKING in perfect graphs. We then present polynomial-time algorithms for several classes of perfect (and related) graphs, including triangulated graphs and their complements, bipartite graphs and their complements, and Seymour graphs. Finally, we discuss various linear programming relaxations for the problem, finding combinatorial dual problems Of CUT PACKING and characterizing the cases in which duality is strong.