Analysis of LP relaxations for multiway and multicut problems

We introduce in this paper an exact nonlinear formulation of the multiway c ut problem. By simple linearizations of this formulation, we derive several well-known and new formulations for the problem. We further establish a co nnection between the multiway cut and the maximum-weighted independent set problem. This leads to the study of several instances of the multiway cut p roblem through the theory of perfect graphs. We also introduce a new random ized rounding argument to study the sharpness of these formulations. (C) 19 99 John Wiley & Sons, Inc.