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 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 krawędzie (których pojemność zostanie zwiększona do nieskończoności), aby zmaksymalizować minimalne cięcie?
ds.algorithms
graph-theory
co.combinatorics
max-flow-min-cut
użytkownik14373
źródło
źródło
Odpowiedzi:
Twierdzenie. Problem w poście jest trudny jak na NP.
Przez „problem w poście” mam na myśli dany wykresG=(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ść n−2 krawędzie, aby wynikowy wykres miał minimalny rozmiar cięcia s . Chodzi o to, żen−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∖C) , potrzebujesz subgrafów wywołanych przez C i V∖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 wykresG=(V,E) , zdefiniuj połączone cięcie jako cięcie(C,V∖C) tak, że podgrupy wywołane przez C i przez V∖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-CutG=(V,E) , pozwolić k=|V|−2 . Aby udowodnić lemat, dowodzimy:
Roszczenie 1: Dla każdegos>0 , jest połączone cięcie (C,V∖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∖C) co najmniej pojemności s . PozwolićT1 i T2 być poddrzewami obejmującymi odpowiednio C i V∖C , a następnie zwiększ pojemność krawędzi w T1 i T2 . (Uwaga:|T1|+|T2|=|C|−1+|V∖C|−1=|V|−2=k .) Jedynym ograniczeniem pojemności skończonej pozostającym na wykresie jest wtedy (C,V∖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 przezk 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órk=n−2 , podgrupa podniesionych krawędzi ma, powiedzmy, dwa połączone elementy C i V∖C , więc jedynym ograniczeniem pojemności skończonej na wynikowym wykresie jest (C,V∖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łkowitejN≥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 ograniczenieP(N) (A Z jednej strony, B z drugiej) ma rozmiar N2 i żaden inny krój nie ma rozmiaru większego niż, powiedzmy, N2−N/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łkav∈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żdegos≥0 , jest cięcie (C,V∖C) 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,V∖C) w G co najmniej pojemności s , rozważ połączone cięcie (A∪C,B∪V∖C) w G′ . To połączone włączyłoG′ tnie przynajmniej s krawędzie od C do V∖C , plus N2 krawędzie od A do B , plus n z 2n krawędzie od V do A∪B .
JEŻELI: Załóżmy, że jest podłączone wycięcieG′ co najmniej wielkości s+N2+n . A i B są po przeciwnych stronach cięcia. (W przeciwnym razie, od drugiego co do wielkościP(N) co najwyżej cięcia N2−N/100 krawędzie w P(N) , całkowita liczba przyciętych krawędzi wynosi co najwyżej N2−N/100+|E|+2|V|≤N2−N/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 A∪B , więc musi być przynajmniej s od C do V∖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.
źródło