Edge disjoint paths and multicut problems in graphs generalizing the trees

National audienceWe generalize all the results obtained for trees in [N. Garg, V. Vazirani, M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut intrees. Algorithmica 18 (1997), pp. 3-20] to graphs with a fixed cyclomatic number. Moreover, we show that, for a fixed number of source-sink pairs, the minimum multicut problem is polynomial-time solvable in planar graphs and in bounded tree-width graphs. Eventually, we introduce the class of k-edge-outerplanar graphs and show that the integrality gap of the maximum edge-disjoint paths problem is bounded in these graphs