Zwiększenie wydajności w celu maksymalizacji minimalnego cięcia

Rozważ wykres ze wszystkimi krawędziami o pojemności jednostkowej. Można znaleźć min. Cięcie w czasie wielomianowym.

Załóżmy, że mogę zwiększyć pojemność dowolnego $k$krawędzie do nieskończoności (równoważne scalaniu węzłów po obu stronach krawędzi). Jaki jest optymalny sposób wyboru optymalnego zestawu$k$ krawędzie (których pojemność zostanie zwiększona do nieskończoności), aby zmaksymalizować minimalne cięcie?

Twierdzenie. Problem w poście jest trudny jak na NP.

Przez „problem w poście” mam na myśli dany wykres $G=(V,E)$ i liczba całkowita $k$, wybierać $k$ krawędzie, aby podnieść pojemność, aby zmaksymalizować minimalne cięcie na zmodyfikowanym wykresie.

Chodzi o redukcję z Max Cut. Z grubsza dany wykres$G=(V,E)$ ma maksymalny rozmiar cięcia $s$ tylko wtedy, gdy możesz zwiększyć pojemność $n-2$ krawędzie, aby wynikowy wykres miał minimalny rozmiar cięcia $s$. Chodzi o to, że$n-2$ krawędzie są wystarczające, aby wymusić na wynikowym wykresie tylko jedno cięcie o skończonej pojemności, i może to być dowolne cięcie.

Ten pomysł nie do końca działa, ponieważ można uzyskać dane cięcie $(C, V\setminus C)$, potrzebujesz subgrafów wywołanych przez $C$ i $V\setminus C$każdy do połączenia. Możesz jednak obejść ten problem za pomocą odpowiedniego gadżetu.

Dowód. Biorąc pod uwagę połączony wykres$G=(V,E)$, zdefiniuj połączone cięcie jako cięcie$(C,V\setminus C)$ tak, że podgrupy wywołane przez $C$ i przez $V\setminus C$każdy jest połączony. Zdefiniuj Max Connected Cut jako problem ze znalezieniem połączonego cięcia (na danym połączonym wykresie) maksymalizującym liczbę krawędzi przecinających cięcie.

Pokazujemy, że Max Connected Cut redukuje problem w poście. Następnie pokazujemy, że nieważone Max Cut redukuje się do Max Connected Cut.

Lemma 1. Max Connected Cut skraca czas poli do problemu określonego w poście.

Dowód. Biorąc pod uwagę instancję Max-Connected-Cut$G=(V,E)$, pozwolić $k=|V|-2$. Aby udowodnić lemat, dowodzimy:

Roszczenie 1: Dla każdego$s>0$, jest połączone cięcie $(C,V\setminus C)$ w $G$ co najmniej pojemności $s$, IFF można podnieść $k$ pojemność krawędzi w $G$ do nieskończoności, tak aby wynikowy wykres miał przynajmniej minimalną wydajność cięcia $s$.

TYLKO JEŻELI: Przypuśćmy, że istnieje połączone cięcie $(C,V\setminus C)$ co najmniej pojemności $s$. Pozwolić$T_1$ i $T_2$ być poddrzewami obejmującymi odpowiednio $C$ i $V\setminus C$, a następnie zwiększ pojemność krawędzi w $T_1$ i $T_2$. (Uwaga:$|T_1|+|T_2|=|C|-1 + |V\setminus C|-1 = |V|-2 = k$.) Jedynym ograniczeniem pojemności skończonej pozostającym na wykresie jest wtedy $(C, V\setminus C)$, o pojemności co najmniej $s$, więc wynikowy wykres ma przynajmniej minimalną wydajność cięcia $s$.

IF: Załóżmy, że można podbić $k$ pojemność krawędzi w $G$ tak, aby wynikowy wykres miał przynajmniej minimalną wydajność cięcia $s$. Rozważ podgraf utworzony przez$k$podniesione krawędzie. Bez utraty ogólności załóż, że ten wykres podrzędny jest acykliczny. (W przeciwnym razie „unise” jedną krawędź z cyklu wypukłych krawędzi i zamiast tego podnieś trochę nie wypukłej krawędzi, która łączy dwa połączone komponenty z podgrafu. Zwiększa to tylko minimalne cięcie na wynikowym wykresie.) Przez wybór$k=n-2$, podgrupa podniesionych krawędzi ma, powiedzmy, dwa połączone elementy $C$ i $V\setminus C$, więc jedynym ograniczeniem pojemności skończonej na wynikowym wykresie jest $(C,V\setminus C)$. I to cięcie ma przynajmniej pojemność$s$, jak na oryginalnym wykresie.

Dowodzi to roszczenia (i lematu). (CO BYŁO DO OKAZANIA)

Dla kompletności pokazujemy, że Max Connected Cut jest NP-zupełny, poprzez redukcję z nieważonego Max Cut.

Lemma 2. Nieważone Max Cut skraca czas poli do Max Connected Cut .

Dowód. Dla dowolnej liczby całkowitej$N\ge 1$, zdefiniuj wykres $P(N)$ składać się z dwóch ścieżek $A$ i $B$, każda o długości $N$, z krawędziami z każdego wierzchołka w $A$ do każdego wierzchołka w $B$. Zostawiamy to jako ćwiczenie dla czytelnika, aby sprawdzić, czy maksymalne ograniczenie$P(N)$ ($A$ Z jednej strony, $B$ z drugiej) ma rozmiar $N^2$i żaden inny krój nie ma rozmiaru większego niż, powiedzmy, $N^2-N/100$.

Oto redukcja. Biorąc pod uwagę każdą nieważoną instancję Max Cut$G=(V,E)$, zbuduj wykres $G'=(V',E')$następująco. Pozwolić$n=|V|$. Pozwolić$N = 100(n^2 + 2n)$. Dodać do$G$ wykres $P(N)$ zdefiniowane powyżej (z dwiema ścieżkami $A$ i $B$). Z każdego wierzchołka$v\in V$ dodaj krawędź do jednego wierzchołka $A$ i drugą krawędź do jednego wierzchołka w $B$. To określa redukcję. Na koniec potwierdzamy, że jest poprawny:

Roszczenie 2: Dla każdego$s\ge 0$, jest cięcie $(C,V\setminus C)$ w $G$ co najmniej pojemności $s$, IFF jest podłączone wycięcie $G'$ co najmniej wielkości $s+N^2+n$.

TYLKO JEŚLI: Biorąc pod uwagę jakiekolwiek cięcie $(C,V\setminus C)$ w $G$ co najmniej pojemności $s$, rozważ połączone cięcie $(A\cup C, B\cup V\setminus C)$ w $G'$. To połączone włączyło$G'$ tnie przynajmniej $s$ krawędzie od $C$ do $V\setminus C$, plus $N^2$ krawędzie od $A$ do $B$, plus $n$ z $2n$ krawędzie od $V$ do $A\cup B$.

JEŻELI: Załóżmy, że jest podłączone wycięcie $G'$ co najmniej wielkości $s+N^2+n$. $A$ i $B$są po przeciwnych stronach cięcia. (W przeciwnym razie, od drugiego co do wielkości$P(N)$ co najwyżej cięcia $N^2-N/100$ krawędzie w $P(N)$, całkowita liczba przyciętych krawędzi wynosi co najwyżej $N^2-N/100 + |E| + 2|V| \le N^2 - N/100 + n^2 + 2n = N^2$.) Pozwolić $C$ oznacz wierzchołki w $V$ z boku cięcia za pomocą $A$. Potem są$N^2$ krawędzie w nacięciu od $A$ do $B$, i $n$ od $V$ do $A\cup B$, więc musi być przynajmniej $s$ od $C$ do $V\setminus C$.

Potwierdza to twierdzenie i Lemma 2. (QED)

Według Lemmas 1 i 2, ponieważ nieważone Max Cut jest trudne NP, problem na słupku jest również trudny NP.