Separation of partition inequalities

Given a graph G = (V,E) with nonnegative weights x(e) for each edge e, a pa rtition inequality is of the form x(delta(S-1,...,S-P)) greater than or equ al to ap+b. Here delta(S-1,...,S-P) denotes the multicut defined by a parti tion S-1,...,S-P of V. Partition inequalities arise as valid inequalities f or optimization problems related to k-connectivity. We give a polynomial al gorithm for the associated separation problem. This is based on an algorith m for finding the minimum of x(delta(S-1,...,S-P))-p that reduces to minimi zing a symmetric submodular function. This is handled with the recent algor ithm of Queyranne. We also survey some applications of partition inequaliti es.