Accueil > Questions Ouvertes > Problème du séparateur : Mohamed Didi-Biha

Problème du séparateur : Mohamed Didi-Biha

lundi 12 mars 2007, par fouilhoux

Problème classique du séparateur

Soit un graphe G=(V,E) avec n=|V|.

Soit une fonction f : V->R.

Soit 1<=b(n)<=n.

Trouver une partition de V en 3 classes (A, B,C) telle que

1<=|A|<=b(n)

1<=|B|<=b(n)

et la coupe [A,B] entre A et B soit vide

avec la somme des f(v) sur tous les sommets v de C soit minimum ($sum_v\in C f(v)$).

Ce problème est NP-difficile même pour les graphes planaires.

Problème Polynomial si b(n)=n-K avec K fixé car il est équivalent à un stable dans un graphe biparti

Problème du séparateur version "coupe"

Soit un graphe G=(V,E) avec n=|V|.

Soit une fonction f : E->R.

Trouver une partition de V en 3 classes (A, B,C) avec A, B et C tous trois non vides.

avec la coupe [A,B] entre A et B soit vide

qui minimise le poids de la coupe issu de C ($f(\delta(C))$).

Quell est la complexité de ce problème ?

Rq : Pour un K fixé, on peut généraliser en autorisant |[A,B]|<=K. Donc pour K=|E|, on retrouve la coupe minimale...

Messages