Nachweis der NP-Härte eines seltsamen Graphpartitionsproblems

7

Ich versuche zu zeigen, dass das folgende Problem NP-schwer ist.

Eingaben: Ganzzahl und verbundener, ungerichteter Graph , ein vertexgewichteter GrapheG=(V,E)

Ausgabe: Partition von , erhalten durch Entfernen aller Kanten von die maximiert werdenGGp=(V,Ep)eE

maxGi{G1,G2,...,Gk}1|Gi|(vjViw(vj))2,

wobei und Elemente von G disjunkt sind. V_i ist die Scheitelpunktmenge für G_i und w (v_j) ist das Gewicht für den Scheitelpunkt v_jGp=G1G2GkG
ViGiw(vj)vj

Einfache englische Erklärung: Wir möchten ein Diagramm partitionieren, indem wir e Kanten entfernen , um ein Ziel zu maximieren. Das Ziel berechnet für jeden der resultierenden disjunkten Untergraphen die Summe der Eckpunkte für den Untergraphen, quadriert diesen Wert und dividiert durch die Kardinalität. Schließlich summieren wir dies über alle Untergraphen.

Bisher habe ich versucht, NP-harte Probleme wie Ratio-Cut, Partition (Nicht-Graph-Problem) und Max Multicut zu reduzieren. Ich habe auch versucht zu zeigen, dass Sonderfälle des Problems NP-schwer sind (weniger ideal). Der Grund, warum ich vermute, dass dieses Problem NP-hart ist (abgesehen davon, dass die meisten Probleme bei der Graphpartitionierung NP-hart sind), ist das Vorhandensein des Kardinalitätsterms und der Kreuzterme zwischen Partitionsgewichten. Alle Eingaben / Problemvorschläge wären hilfreich. Ein NP-harter Beweis für jede Art von spezifischem Diagramm wäre nützlich.

Optimierer
quelle
Versuchen Sie, das Teilmengenproblem zu reduzieren?
Xiamx
2
Damit G1,G2,,Gk sollen die verbundenen Komponenten des Graphen sein Gp=(V,ER), wo RE befriedigend |R|=eist die Menge der entfernten Kanten?
David Eisenstat
@ DW Ich habe es versucht. Ich habe mehr Probleme mit dem Kardinalitätsbegriff als mit dem Quadrieren. Für das Quadrieren denke ich, dass es möglich sein könnte, ein Diagramm zu erstellen, bei dem die Kreuzterme in der Lösung verschwinden, indem positiv und negativ gewichtete Kanten in einem Ketten- oder Gitterdiagramm abgewechselt werden
Optimizer
@ DavidEisenstat ja
Optimierer
@xiamx Sei vorsichtig; Sie sollten reduzieren von einem Problem , das hart ist, und nicht umgekehrt.
Juho

Antworten:

2

Lassen Sie uns das Problem der Mehrwegschnitte reduzieren, eine Variante des Minimumsk-Schnitt zu Ihrem Problem. Berücksichtigen Sie insbesondere das Problem des minimalen 3-Wege-Schnitts, das für alle Kantengewichte gleich 1 NP-hart ist (siehe Die Komplexität von Mehrwegschnitten ).

Ein (minimales) 3-Wege-Schnittproblem ist: gegebene Grafik G=(V,E) und Terminals s1,s2,s3V, finden Sie einen minimalen Satz von Kanten EE so dass die Entfernung von E von E trennt jedes Terminal sivon den Anderen. Die Entscheidungsversion besteht darin, herauszufinden, ob eine Trennung möglich ists1,s2,s3 durch Entfernen von nicht mehr als w Kanten, wo w ist ein Teil der Eingabe.

Gegebenes Diagramm G, Terminals s1,s2,s3 und ganze Zahl wmöchten wir das 3-Wege-Schnittproblem auf Ihr "seltsames Graphpartitionsproblem" reduzieren. Für jedes Terminalsi, Wir fügen hinzu Nmehr verteces, um seine Nachbarn zu sein. Wie der Name andeutet,Nwäre eine ausreichend große Zahl. Das Gewicht aller Verteces ist 0 mit Ausnahme vons1,s2,s3, deren Gewichte sind 1,10,100bzw. Bezeichnen Sie dieses neue Diagramm mitG. Es ist klar, dasss1,s2,s3 kann durch Entfernen getrennt werden w Kanten in G genau dann, wenn sie durch Entfernen getrennt werden können w Kanten in G.

Wenn eine Partition Gp von G trennt die Verbindung s1,s2,s3ist seine Punktzahl ungefähr 10101/Noder genauer gesagt nicht weniger als

10101N+n
als der Teil enthält si hat nicht mehr als N+n verteces, wo n is the number of verteces in G. On the other hand, if a partition Gp fails to disconnect s1,s2,s3, its score is no more than
10060.5Nw
. When N is sufficiently large, 10101N+n>10060.5Nw, so G can be 3-way partitioned by removing w edges if and only if G has a partition removing w edges, whose score is at least 10101N+n.
Tianren Liu
quelle
@Optimizer, in the original problem, minimum 3-way cut, vertex has no weight. So it's not possible to restrict its input on vertex weight. On the other hand, your problem involves weighted vertex. So the above proof shows that your problem is NP-complete even if you restrict the input s.t. most verteces have zero weight.
Tianren Liu
There is no terminal in the minimum k-cut problem. Are you sure about the NP-complete of the problem you put there?
InformedA
@randomA, minimum k-cut problem has several variants. One variant includes k terminals as part of the input, the goal is find minimum cost k-cut that disconnects these kTerminals. Diese Variante wird in dem von mir zitierten Artikel als Mehrwegschnittproblem bezeichnet. Ich sollte es in meiner Antwort klarstellen, danke für Ihren Kommentar.
Tianren Liu
@randomA Dies hat eine gute Beschreibung dieser Version des Problems: math.mit.edu/~goemans/18434S06/multicuts-brian.pdf
Optimizer