Nachweis der NP-Härte eines seltsamen Graphpartitionsproblems

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

Eingaben: Ganzzahl und verbundener, ungerichteter Graph , ein vertexgewichteter Graph $e$ $G=(V,E)$

Ausgabe: Partition von , erhalten durch Entfernen aller Kanten von die maximiert werden $G$ $G_p=(V,E_p)$ $e$ $E$

$max \sum_{G_{i} \in {G_{1}, G_{2}, . . ., G_{k}}} \frac{1}{| G_{i} |} {(\sum_{v_{j} \in V_{i}} w (v_{j}))}^{2},$ $\max \sum\limits_{G_i \in \{G_1,G_2,...,G_k\}} \frac1{|G_i|}\left(\sum_{v_j \in V_i}w(v_j)\right)^{\!2},$
wobei und Elemente von disjunkt sind. ist die Scheitelpunktmenge für und ist das Gewicht für den Scheitelpunkt $G_p=G_1 \cup G_2 \cup \dots \cup G_k$ $G$
$V_i$ $G_i$ $w(v_j)$ $v_j$

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.

algorithms complexity-theory np-hard set-cover Optimierer
quelle

Versuchen Sie, das Teilmengenproblem zu reduzieren?

Xiamx

Damit

G_{1}, G_{2}, \dots, G_{k}

$G_1,G_2,\ldots,G_k$ sollen die verbundenen Komponenten des Graphen sein

G_{p} = (V, E - R)

$G_p=(V,\:E-R)$ , wo

R \subseteq E

$R\subseteq E$ befriedigend

| R | = e

$\lvert R\rvert=e$ ist 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:

Lassen Sie uns das Problem der Mehrwegschnitte reduzieren, eine Variante des Minimums $k$ -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 $s_1,s_2,s_3\in V$ , finden Sie einen minimalen Satz von Kanten $E'\subseteq E$ so dass die Entfernung von $E'$ von $E$ trennt jedes Terminal $s_i$ von den Anderen. Die Entscheidungsversion besteht darin, herauszufinden, ob eine Trennung möglich ist $s_1,s_2,s_3$ durch Entfernen von nicht mehr als $w$ Kanten, wo $w$ ist ein Teil der Eingabe.

Gegebenes Diagramm $G$ , Terminals $s_1,s_2,s_3$ und ganze Zahl $w$ möchten wir das 3-Wege-Schnittproblem auf Ihr "seltsames Graphpartitionsproblem" reduzieren. Für jedes Terminal $s_i$ , Wir fügen hinzu $N$ mehr verteces, um seine Nachbarn zu sein. Wie der Name andeutet, $N$ wäre eine ausreichend große Zahl. Das Gewicht aller Verteces ist 0 mit Ausnahme von $s_1,s_2,s_3$ , deren Gewichte sind $1,10,100$ bzw. Bezeichnen Sie dieses neue Diagramm mit $G'$ . Es ist klar, dass $s_1,s_2,s_3$ 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 $G'_p$ von $G'$ trennt die Verbindung $s_1,s_2,s_3$ ist seine Punktzahl ungefähr $10101/N$ oder genauer gesagt nicht weniger als

\frac{10101}{N + n}

$\frac{10101}{N+n}$ als der Teil enthält

s_{i}

$s_i$ hat nicht mehr als

N + n

$N+n$ verteces, wo

n

$n$ is the number of verteces in

G

$G$ . On the other hand, if a partition

G_{p}^{'}

$G'_p$ fails to disconnect

s_{1}, s_{2}, s_{3}

$s_1,s_2,s_3$ , its score is no more than

\frac{10060.5}{N - w}

$\frac{10060.5}{N-w}$ . When

N

$N$ is sufficiently large,

\frac{10101}{N + n} > \frac{10060.5}{N - w}

$\frac{10101}{N+n} > \frac{10060.5}{N-w}$ , so

G

$G$ can be 3-way partitioned by removing

w

$w$ edges if and only if

G^{'}

$G'$ has a partition removing

w

$w$ edges, whose score is at least

\frac{10101}{N + n}

$\frac{10101}{N+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

$k$ -cut problem has several variants. One variant includes

k

$k$ terminals as part of the input, the goal is find minimum cost

k

$k$ -cut that disconnects these

k

$k$ Terminals. 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