Separation of Partition Inequalities

Given a graph G = (V, E) with nonnegative weights x(e) for each edge e, a partition inequality is of the form x(δ(S₁,…,S_p)) ≥ ap + b. Here δ(S₁,…,S_p) denotes the multicut defined by a partition S₁,…,S_p of V. Partition inequalities arise as valid inequalities for optimization problems related to k-connectivity. We give a polynomial algorithm for the associated separation problem. This is based on an algorithm for finding the minimum of x(δ(S₁,…,S_p)) − p that reduces to minimizing a symmetric submodular function. This is handled with the recent algorithm of Queyranne. We also survey some applications of partition inequalities.