Augmenter la capacité pour maximiser la coupe minimale

9

Considérons un graphique avec tous les bords ayant une capacité unitaire. On peut trouver la coupure min en temps polynomial.

Supposons que je suis autorisé à augmenter la capacité de n'importe quel bords à l'infini (équivalent à la fusion des nœuds de chaque côté du bord). Quelle est la façon optimale de sélectionner un ensemble optimal de arêtes (dont la capacité sera augmentée à l'infini) pour maximiser la coupe minimale?kk

user14373
la source
Je ne suis pas sûr de comprendre votre question: par "Quelle est la façon optimale de sélectionner k de telles arêtes pour maximiser la coupe minimale?", Vous voulez dire la coupe minimale de 1) un graphique avec des capacités unitaires ou 2) un graphique avec des capacités générales ?
Jeremy

Réponses:

3

Théorème. Le problème dans le message est NP-difficile.

Par "le problème dans le post", je veux dire, étant donné un graphique et un entier , choisir bords pour augmenter les capacités de manière à maximiser la coupe minimale dans le graphique modifié.k kG=(V,E)kk

L'idée est de réduire à partir de Max Cut. En gros, un graphique donné a une taille de coupe maximale si et seulement si vous pouvez augmenter les capacités des bords sorte que le graphique résultant ait une taille de coupe minimale . L'idée est que arêtes sont juste suffisantes pour forcer le graphique résultant à n'avoir qu'une seule coupe de capacité finie, et cela peut être n'importe quelle coupe que vous choisissez.s n - 2 s n - 2G=(V,E)sn2sn2

Cette idée ne fonctionne pas vraiment car pour obtenir une coupe donnée , vous avez besoin que les sous-graphiques induits par et soient connectés. Mais vous pouvez contourner ce problème avec un gadget approprié.C V C(C,VC)CVC

Preuve. Étant donné un graphe connecté , définissez une coupe connectée comme étant une coupe telle sorte que les sous-graphiques induits par et par soient chacun connectés. Définissez Max Connected Cut comme étant le problème de trouver une coupe connectée (dans un graphique connecté donné) maximisant le nombre d'arêtes traversant la coupe.( C , V C ) C V CG=(V,E)(C,VC)CVC

Nous montrons que Max Connected Cut se réduit au problème dans le message. Ensuite, nous montrons que Max Cut non pondéré se réduit à Max Connected Cut.

Lemme 1. Max Connected Cut réduit en temps poly au problème défini dans l'article.

Preuve. Étant donné une instance Max-Connected-Cut , soit . Pour prouver le lemme, nous prouvons ce qui suit:k = | V | - 2G=(V,E)k=|V|2

Revendication 1: pour tout , il y a une coupure connectée dans de capacité au moins , IFF il est possible d'augmenter capacités de bord en à l'infini de sorte que le graphique résultant ait min capacité de coupe au moins .( C , V C ) G s k G ss>0(C,VC)GskGs

SEULEMENT SI: Supposons qu'il y ait une coupure connectée de capacité au moins . Soit et sous-arbres couvrant respectivement et , puis augmentez les capacités des arêtes dans et . (Notez que .) La seule réduction de capacité finie restante dans le graphique est alors , d'une capacité d'au moins , de sorte que le graphique résultant a une capacité de coupe minimale d'au moins .(C,VC)sT1T2CVCT1T2|T1|+|T2|=|C|1+|VC|1=|V|2=k(C,VC)ss

IF: Supposons qu'il soit possible d'augmenter capacités de bord en sorte que le graphique résultant ait une capacité de coupe minimale d'au moins . Considérons le sous-graphique formé par les bords surélevés. Sans perte de généralité, supposons que ce sous-graphique soit acyclique. (Sinon, "décompressez" une arête d'un cycle d'arêtes surélevées et relevez plutôt une arête non lissée qui joint deux composants connectés du sous-graphique. Cela ne fait qu'augmenter la coupe minimale dans le graphique résultant.) Par le choix de , le sous-graphique des bords surélevés a deux composants connectés, disons et , donc la seule coupe de capacité finie dans le graphique résultant estkGskk=n2CVC(C,VC). Et cette coupe a une capacité d'au moins , comme dans le graphique d'origine.s

Cela prouve la revendication (et le lemme). (QED)

Pour être complet, nous montrons que Max Connected Cut est NP-complet, par réduction de Max Cut non pondéré.

Lemme 2. Max Cut non pondéré réduit le temps de poly à Max Connected Cut .

Preuve. Pour tout entier , définie graphique pour se composent de deux voies et , chacun de longueur , avec les bords de chaque sommet à chaque sommet . Nous laissons un exercice au lecteur pour vérifier que la coupe maximale de ( d'un côté, de l'autre) a la taille , et aucune autre coupe n'a une taille plus grande que, disons, .N1P(N)ABNABP(N)ABN2N2N/100

Voici la réduction. Étant donné toute instance Max Cut non pondérée , construisez un graphique comme suit. Soit. Soit . Ajoutez à le graphique défini ci-dessus (avec ses deux chemins et ). A partir de chaque sommet ajouter un bord à un sommet en et un autre bord d'un sommet dans . Ceci définit la réduction. Pour finir, nous prouvons que c'est correct:G=(V,E)G=(V,E)n=|V|N=100(n2+2n)GP(N)ABvVAB

Revendication 2: pour tout , il y a une coupe en de capacité au moins , IFF il y a une coupe connectée en de taille au moins .s0(C,VC)GsGs+N2+n

SEULEMENT SI: étant donné toute coupe en de capacité au moins , considérez la coupe connectée en . Cette coupe branché coupures au moins bords de à , plus arêtes de à , ainsi des arêtes de à .(C,VC)Gs(AC,BVC)GGsCVCN2ABn2nVAB

SI: Supposons qu'il existe une coupe connectée en de taille au moins . et sont sur les côtés opposés de la coupe. (Sinon, étant donné que la deuxième plus grande coupe de coupe au plus bords en , le nombre total de bords coupés est au plus ) Soit. désignent les sommets de sur le côté de la coupe avec . Ensuite, il y a bords dans la coupe de à , et de àGs+N2+nABP(N)N2N/100P(N)N2N/100+|E|+2|V|N2N/100+n2+2n=N2CVAN2An V A B s C V CBnVAB , alors il doit y avoir au moins de à .sCVC

Cela prouve la revendication et le lemme 2. (QED)

Par Lemmas 1 et 2, comme Max Cut non pondéré est NP-difficile, le problème dans le poste est également NP-difficile.

Neal Young
la source
Cela montre également que le problème de "l'incrémentation de k bords pour maximiser la coupe st" pour et donnés est NP-complet (choisissez et pour être des sommets dans et respectivement). t s t A BststAB
daniello