On the separation of partition inequalities

On the separation of partition inequalities
Mohamed Didi Biha
mohamed.didi-biha@univ-avignon.fr
Ali Ridha Mahjoub
Ridha.Mahjoub@math.univ-bpclermont.fr
Lise Slama
lise.slama@isima.fr
Laboratoire d’Analyse non lineaire´ et Geom´ etrie,´ Universite´ d’Avignon
339, chemin des Meinajaries,` 84911 Avignon Cedex 9
LIMOS-CNRS 6158, Universite´ de Clermont-Ferrand II
Complexe Scientifique des Cezeaux,´ 63177 Aubiere` Cedex, France
Abstract
Given a graph with nonnegative weights for each edge , a partition in-
equality is of the form . Here denotes the multicut
defined by of . Partition inequalities arise as valid inequalities for optimization
problems related to -connectivity. In this paper, we will show that, if decomposes into
by 1 and 2-node cutsets, then the separation problem for the partition inequalities
on can be solved by mean of a polynomial time combinatorial algorithm provided that such
an algorithm exists for where are graphs related to . We
will also discuss some applications.
Keywords: separation problem, partition inequalities, graph connectivity
1 Introduction
Given a graph , a subset of nodes whose cardinality is , is called a
-node cutset if the removal of ...