Algorithme efficace pour couper min avec nombre spécifié de sommets

Question

considérer un graphique avec des sommets $ V $ et bords $ E $ . La version standard du problème de coupe MIN consiste à trouver la partition de $ v $ dans un sous-ensemble (non vide) $ C $ et son complément $ \ bar {c} $ $ de manière à minimiser le nombre de bords entre $ C $ et $ \ bar {c} $ . Les algorithmes sont connus pour ce problème qui le résolvent en temps polynomial. Ma question est que si on spécifie en outre la contrainte que $ | C |= N $ pour certains $ n <| v | $ ? C'est-à-dire que nous souhaitons trouver l'ensemble de N $ N $ avec le nombre minimal d'arêtes qui le connectent au reste des sommets. Y a-t-il également des algorithmes efficaces pour ce cas? Je suis intéressé à la fois dans la question de savoir si ce problème est officiellement résoluble en temps polynomial (que je devinerais que c'est) et dans quels algorithmes sont les meilleurs dans la pratique.

Answer 1

pour $ n=frac {| v |} 2 $ , c'est ce qu'on appelle une bisection minimale, et c'est NP-Hard. Il existe une $ o (\ log ^ {3/2} n) $ -approximation: " une approximation polylogarithmique de la bisection minimale ".

Si vous êtes intéressé, le problème le plus général se divise en plusieurs composants de la même taille, ce qui s'appelle un partitionnement de graphique équilibré. Pour plus de 2 parties, aucune approximation finie n'existe que si p= np: "Partition de graphique équilibré" (Andreev, Rakke) , puisque vous ne pouvez pas vérifier efficacement si la réponse est 0.

Si les pièces ne sont pas nécessairement exactement équilibrées (un petit déséquilibre est autorisé), une $ O (\ journal n) $ algorithme d'appoint existe: "Partitions équilibrées des arbres et des applications" .

---

Certains algorithmes (également vérifier https://fr.wikipedia.org/wiki/graph_partition et des sections "références" des documents suivants):

• Recherche locale avec diverses saveurs: nous commençons avec une partitionnement, puis essayons d'échanger des sommets entre les pièces afin de minimiser la coupe. Par exemple. Nous calculons "gain" pour chaque sommet (amélioration si nous le déplacons dans une autre partie) et échangez des sommets avec le gain maximum. Son avantage est que vous pouvez l'appliquer après tout autre algorithme.

• partitionnement spectral (voir par exemple Théorie et graphique spectrales Partitionnement ): utilise le deuxième vecteur propre d'une matrice laplacienne pour se rapprocher de la partitionnement (par exemple, en déplaçant la plus petite classe $ | v | / 2 $ coordonnées au premier partie). Fonctionne étonnamment bien. Cependant, je ne suis pas sûr qu'il puisse être adapté à l'affaire lorsque vous souhaitez une bisection non équilibrée (par exemple 1: 2 $ au lieu de 1 $: 1 $ ).

• Intégration linéaire: "Distribué une partitionnement équilibré via une incorporation linéaire" . Nous intégrons des sommets dans une matrice unidimensionnelle tout en minimisant la somme sur toutes les paires de sommets: la distance entre eux multiplié par le poids de leur bord. Ensuite, nous venons de scinder ce tableau en morceaux consécutifs de tailles requises. N'a pas fonctionné bien dans mon expérience.

• (annonces) Notre papier: "Graphique équilibré multidimensionnel Partitionnement via Descente de gradient projetée ", où nous avons utilisé une descente de gradient pour trouver une bisection minimale: Pour chaque sommet, nous introduisons une variable qui représente environ une probabilité que le sommet appartient à la première partie et la réduction de la coupe diminue à l'optimisation contrainte d'un Fonction quadratique. C'est un peu surperformé dans la pratique par une recherche locale précise, mais cela fonctionne vraiment bien lorsque vous avez des contraintes de solde multiples.

Mis à part la méthode spectrale, toutes peuvent être de manière trivialement adaptée pour partitionnement du graphique dans les proportions arbitraires.

Il existe également des solveurs standard: Kihip , Metis . De mon expérience, Kaih était plutôt bonne. Je ne suis pas sûr qu'ils soutiennent la division en parties de tailles arbitraires cependant.