Given an undirected graph G with n nodes and m edges, we address the problem of finding a largest collection of edge-disjoint cuts} in G. In particular, we study the complexity of the problem, dubbed Cut Packing (CP), about which very little is known although it is natural and has practical applications. We show a very close relationship with Independent Set (IS), 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 IS immediately extends to CP by loosing a factor 2. In particular, this yields a 2-approximation algorithm for CP 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 two combinatorial dual problems of CP and characterizing the cases in which duality is strong.
Packing Cuts in Undirected Graphs
CAPRARA, ALBERTO;
2004
Abstract
Given an undirected graph G with n nodes and m edges, we address the problem of finding a largest collection of edge-disjoint cuts} in G. In particular, we study the complexity of the problem, dubbed Cut Packing (CP), about which very little is known although it is natural and has practical applications. We show a very close relationship with Independent Set (IS), 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 IS immediately extends to CP by loosing a factor 2. In particular, this yields a 2-approximation algorithm for CP 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 two combinatorial dual problems of CP and characterizing the cases in which duality is strong.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
