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

9

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 kkrawędzie do nieskończoności (równoważne scalaniu węzłów po obu stronach krawędzi). Jaki jest optymalny sposób wyboru optymalnego zestawuk krawędzie (których pojemność zostanie zwiększona do nieskończoności), aby zmaksymalizować minimalne cięcie?

użytkownik14373
źródło
Nie jestem pewien, czy rozumiem twoje pytanie: „Jaki jest optymalny sposób wyboru k takich krawędzi, aby zmaksymalizować minimalne cięcie?”, Masz na myśli minimalne cięcie 1) wykresu o jednostkowych pojemnościach lub 2) wykresu o ogólnych zdolnościach ?
Jeremy

Odpowiedzi:

3

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 wykresG=(V,E) ma maksymalny rozmiar cięcia s tylko wtedy, gdy możesz zwiększyć pojemność n2 krawędzie, aby wynikowy wykres miał minimalny rozmiar cięcia s. Chodzi o to, żen2 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,VC), potrzebujesz subgrafów wywołanych przez C i VCkażdy do połączenia. Możesz jednak obejść ten problem za pomocą odpowiedniego gadżetu.

Dowód. Biorąc pod uwagę połączony wykresG=(V,E), zdefiniuj połączone cięcie jako cięcie(C,VC) tak, że podgrupy wywołane przez C i przez VCkaż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-CutG=(V,E), pozwolić k=|V|2. Aby udowodnić lemat, dowodzimy:

Roszczenie 1: Dla każdegos>0, jest połączone cięcie (C,VC) 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,VC) co najmniej pojemności s. PozwolićT1 i T2 być poddrzewami obejmującymi odpowiednio C i VC, a następnie zwiększ pojemność krawędzi w T1 i T2. (Uwaga:|T1|+|T2|=|C|1+|VC|1=|V|2=k.) Jedynym ograniczeniem pojemności skończonej pozostającym na wykresie jest wtedy (C,VC), 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 przezkpodniesione 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órk=n2, podgrupa podniesionych krawędzi ma, powiedzmy, dwa połączone elementy C i VC, więc jedynym ograniczeniem pojemności skończonej na wynikowym wykresie jest (C,VC). 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łkowitejN1, 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 ograniczenieP(N) (A Z jednej strony, B z drugiej) ma rozmiar N2i żaden inny krój nie ma rozmiaru większego niż, powiedzmy, N2N/100.

Oto redukcja. Biorąc pod uwagę każdą nieważoną instancję Max CutG=(V,E), zbuduj wykres G=(V,E)następująco. Pozwolićn=|V|. PozwolićN=100(n2+2n). Dodać doG wykres P(N) zdefiniowane powyżej (z dwiema ścieżkami A i B). Z każdego wierzchołkavV 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żdegos0, jest cięcie (C,VC) w G co najmniej pojemności s, IFF jest podłączone wycięcie G co najmniej wielkości s+N2+n.

TYLKO JEŚLI: Biorąc pod uwagę jakiekolwiek cięcie (C,VC) w G co najmniej pojemności s, rozważ połączone cięcie (AC,BVC) w G. To połączone włączyłoG tnie przynajmniej s krawędzie od C do VC, plus N2 krawędzie od A do B, plus n z 2n krawędzie od V do AB.

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

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.

Neal Young
źródło
Pokazuje to również, że dla danego problemu występuje problem „zwiększania krawędzi k, aby zmaksymalizować cięcie” s i t jest kompletny NP (wybierz s i t być wierzchołkami A i bodpowiednio).
daniello