Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width

The Multicut problem can be defined as: given a graph G and a collection of pairs of distinct vertices {s_i,t_i} of G, find a minimum set of edges of G whose removal disconnects each s_i from the corresponding t_i. Multicut is known to be NP-hard and Max SNP-hard even when the input graph is restricted to being a tree. The main result of the paper is a polynomial-time approximation scheme (PTAS) for Multicut in unweighted graphs with bounded degree and bounded tree-width. That is, for any ε>0, we present a polynomial-time (1+ε)-approximation algorithm. In the particular case when the input is a bounded-degree tree, we have a linear-time implementation of the algorithm. We also provide some hardness results: we prove that Multicut is still NP-hard for binary trees and that it is Max SNP-hard if we drop any of the three conditions (unweighted, bounded-degree, bounded tree-width). Finally we show that some of these results extend to the vertex version of Multicut and to a directed version of Multicut.     

Improving multicut in directed trees by upgrading nodes

In this paper, we consider the network improvement problem for multicut by upgrading nodes in a directed tree T = (V, E) with multiple sources and multiple terminals. In a node based upgrading model, a node v can be upgraded at the expense of c(v) and such an upgrade reduces weights on all edges incident to v. The objective is to upgrade a minimum cost subset S ⊆ V of nodes such that the resulting network has a multicut in which no edge has weight larger than a given value D. We first obtain a minimum cardinality node multicut V_c for tree T, then find the minimum cost upgrading set based on the upgrading sets for the subtrees rooted at the nodes in V_c. We show that our algorithm is polynomial when the number of source–terminal pairs is upper bounded by a given value.     

Exact algorithms and applications for Tree-like Weighted Set Cover

We introduce an NP-complete special case of the Weighted Set Cover problem and show its fixed-parameter tractability with respect to the maximum subset size, a parameter that appears to be small in relevant applications. More precisely, in this practically relevant variant we require that the given collection C of subsets of a base set S should be “tree-like”. That is, the subsets in C can be organized in a tree T such that every subset one-to-one corresponds to a tree node and, for each element s of S, the nodes corresponding to the subsets containing s induce a subtree of T. This is equivalent to the problem of finding a minimum edge cover in an edge-weighted acyclic hypergraph. Our main result is an algorithm running in O(3^kmn) time where k denotes the maximum subset size, n:=|S|, and m:=|C|. The algorithm also implies a fixed-parameter tractability result for the NP-complete Multicut in Trees problem, complementing previous approximation results. Our results find applications in computational biology in phylogenomics and for saving memory in tree decomposition based graph algorithms.     

Computing minimum multiway cuts in hypergraphs

The hypergraph $k$-cut problem is the problem of finding a minimum capacity set of hyperedges whose removal divides a given hypergraph into at least $k$ connected components. We present an algorithm for this problem, that runs in strongly polynomial time if both $k$ and the maximum size of the hyperedges are constants. Our algorithm extends the algorithm proposed by Thorup (2008) for computing minimum $k$-cuts of graphs from greedy packings of spanning trees.     

Covering problems in edge- and node-weighted graphs

This paper discusses the graph covering problem in which a set of edges in an edge- and node-weighted graph is chosen to satisfy some covering constraints while minimizing the sum of the weights. In this problem, because of the large integrality gap of a naive linear programming (LP) relaxation, LP rounding algorithms based on the relaxation yield poor performance. Here we propose a stronger LP relaxation for the graph covering problem. The proposed relaxation is applied to designing primal–dual algorithms for two fundamental graph covering problems: the prize-collecting edge dominating set problem and the multicut problem in trees. Our algorithms are an exact polynomial-time algorithm for the former problem, and a 2-approximation algorithm for the latter problem. These results match the currently known best results for purely edge-weighted graphs.     

Adaptive multicut aggregation for two-stage stochastic linear programs with recourse

Outer linearization methods for two-stage stochastic linear programs with recourse, such as the L-shaped algorithm, generally apply a single optimality cut on the nonlinear objective at each major iteration, while the multicut version of the algorithm allows for several cuts to be placed at once. In general, the L-shaped algorithm tends to have more major iterations than the multicut algorithm. However, the trade-offs in terms of computational time are problem dependent. This paper investigates the computational trade-offs of adjusting the level of optimality cut aggregation from single cut to pure multicut. Specifically, an adaptive multicut algorithm that dynamically adjusts the aggregation level of the optimality cuts in the master program, is presented and tested on standard large-scale instances from the literature. Computational results reveal that a cut aggregation level that is between the single cut and the multicut can result in substantial computational savings over the single cut method.     

Multicuts and integral multiflows in rings

We show how to solve in polynomial time the multicut and the maximum integral multiflow problems in rings. Moreover, we give linear-time procedures to solve both problems in rings with uniform capacities.