We study the complexity and approximability of Cut Packing and Cycle Packing. For Cycle Packing, we show that the problem is APX-hard but can be approximated within a factor of O(log n) by a simple greedy approach. Essentially the same approach achieves constant approximation for “dense” graphs. We show that both problems are NP-hard for planar graphs. For Cut Packing we show that, given a graph G the maximum cut packing is always between α(G) and 2α(G). We then derive new or improved polynomial-time algorithms for Cut Packing for special classes of graphs.
Packing Cycles and Cuts in Undirected Graphs
RIZZI, ROMEO
2001-01-01
Abstract
We study the complexity and approximability of Cut Packing and Cycle Packing. For Cycle Packing, we show that the problem is APX-hard but can be approximated within a factor of O(log n) by a simple greedy approach. Essentially the same approach achieves constant approximation for “dense” graphs. We show that both problems are NP-hard for planar graphs. For Cut Packing we show that, given a graph G the maximum cut packing is always between α(G) and 2α(G). We then derive new or improved polynomial-time algorithms for Cut Packing for special classes of graphs.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
