Informatyczny kącik olimpijski

Podział grafu

Jednym z najtrudniejszych zadań, z którym mierzyli się uczestnicy światowych finałów konkursu ACM ICPC w roku 2014, było zadanie pt. Metal Processing Plant.

Zadanie. Dany jest $n$ -wierzchołkowy $|(n⩽ 200)$ nieskierowany graf pełny. Dla każdej krawędzi $| uv$ grafu znamy jej wagę $| d(u,v).$ Wagą podzbioru wierzchołków $S$ nazwiemy maksymalną wagę krawędzi po wszystkich parach wierzchołków z tego podzbioru, tzn.

d(S) = maxu,v> Sd(u,v).

Należy znaleźć podział wierzchołków grafu na dwa podzbiory $|A, B,$ których sumaryczna waga $d(A) +d(B)$ jest jak najmniejsza.

Załóżmy na początek, że zdecydowaliśmy, iż podzielimy graf na dwa podzbiory o wagach nie większych niż ustalone liczby $dA$ i $dB, |$ i chcemy stwierdzić, czy da się to zrobić. Innymi słowy, chcemy znaleźć dwa podzbiory $|A$ i $B,$ że $d(A) ⩽ dA$ i $d(B) | ⩽ dB.$ Dla każdego wierzchołka $|u$ wprowadźmy zmienną logiczną $|xu,$ która oznaczać będzie, czy wierzchołek $u$ należy do podzbioru $B.$ Skonstruujemy teraz listę zdań logicznych, które zakodują ograniczenia na wartości zmiennych.

Każda z krawędzi $uv$ łączy dwa wierzchołki z podzbioru $A$ (wtedy $|d(u,v) ⩽ dA$ ), dwa wierzchołki z podzbioru $B |$ (wtedy $d(u, v)⩽ dB$ ) lub wierzchołki należące do różnych podzbiorów (i wtedy nie mamy ograniczenia na wagę tej krawędzi). Załóżmy bez straty ogólności, że $|dA⩽dB.$

(1): Jeśli $d(u, v)⩽ dA,$ to wierzchołki $u, v$ mogą znajdować się gdziekolwiek.
(2): Jeśli $|dA< d(u, v) ⩽dB,$ to co najmniej jeden z wierzchołków $|u, v$ musi znajdować się w podzbiorze $|B,$ czyli musi być spełniona alternatywa $|xu∨ xv.$
(3): Jeśli $dB < d(u, v),$ to wierzchołki $|u,v$ muszą znajdować się w różnych podzbiorach, czyli muszą być spełnione obie alternatywy $xu ∨xv$ oraz $¬ xu∨ ¬xv.$

Każda z alternatyw zawiera dwie zmienne (lub ich negacje), zatem do znalezienia takich wartości zmiennych, które spełniają wszystkie alternatywy, możemy użyć algorytmu 2-SAT. Algorytm ten działa w czasie liniowym od liczby zmiennych i alternatyw, w naszym przypadku będzie to zatem czas $2 O(n ).$

Jesteśmy już gotowi zaproponować pierwsze rozwiązanie naszego zadania. Ponieważ waga podzbioru jest równa wadze jednej z krawędzi grafu, więc mamy $|O(n2)$ możliwości wyboru każdej z liczb $dA$ i $dB. |$ Sprawdzenie dla wszystkich tych wyborów, czy istnieje podział, i wybranie podziału dla najmniejszej sumy $d +d A B$ daje rozwiązanie działające w czasie $O(n6).$ Jednak wybory te nie są zupełnie niezależne. Zauważmy, że jeśli dla pewnej pary $|dA, dB$ podział istnieje, to istnieje też dla pary o większych wartościach. Zatem dla ustalonej wartości $dB,$ którą wybierzemy na $|O(n2)$ sposobów, możemy znaleźć najmniejszą wartość $|d , A$ używając wyszukiwania binarnego w czasie $O(logn).$ To da nam rozwiązanie działające w czasie $|O(n4logn).$

Okazuje się, że możemy istotnie zmniejszyć liczbę kandydatów na wartość $|dB.$ Powiemy, że krawędź $uv$ jest wewnętrzna, jeśli oba wierzchołki $|u, v$ znajdują się w tym samym podzbiorze. Załóżmy, że znaleźliśmy maksymalne drzewo rozpinające grafu. Każda krawędź $|uv$ nienależąca do tego drzewa wyznacza cykl (w którym pozostałe krawędzie należą do drzewa). Jeśli cykl ten ma nieparzystą długość, to co najmniej jedna z jego krawędzi musi być wewnętrzna. Z kolei jeśli cykl ten ma parzystą długość i zawiera jakąś krawędź wewnętrzną, to musi zawierać co najmniej dwie takie krawędzie (a więc co najmniej jedną krawędź drzewową).

Załóżmy, że $| dB = d(u, v)$ nie jest równe wadze żadnej krawędzi z maksymalnego drzewa rozpinającego, w szczególności krawędź wewnętrzna $|uv$ nie należy do drzewa. Jeśli ta krawędź wyznacza cykl długości parzystej, to na tym cyklu znajduje się jeszcze jedna krawędź wewnętrzna $|xy.$ Ale wtedy $| dB⩾ d(x, y) > d(u, v),$ co daje sprzeczność. Zatem krawędź $| uv$ wyznacza cykl długości nieparzystej. Rozważmy krawędź niedrzewową $|xy$ wyznaczającą nieparzysty cykl, taką że waga $|d(x,y)$ jest maksymalna; zatem $|d(x,y) ⩾ d(u,v).$ Ponieważ $|d(x,y)$ jest minimalną wagą na tym cyklu i cykl ten zawiera krawędź wewnętrzną, to $| dB⩾ d(x, y).$ Tak więc w tym przypadku $|d(u,v) = d(x,y).$

Z tego wynika, że mamy $| O(n)$ kandydatów na wartość $| dB.$ Są to wagi wszystkich krawędzi należących do drzewa oraz maksimum z wag krawędzi niedrzewowych tworzących cykle o nieparzystej długości. Drzewo rozpinające można znaleźć algorytmem Kruskala w czasie $O(n log n).$ Jeśli wykonamy dwukolorowanie tego drzewa w czasie $| O(n),$ to będziemy mogli dla każdej niedrzewowej krawędzi odpowiadać w czasie stałym, czy tworzy ona cykl nieparzystej długości.

Ostatecznie dostajemy algorytm działający w czasie $3 O(n logn).$