W rozwiązaniach pojawiły się dwa podejścia.
Zacznę od nieco bardziej naturalnego. Dla do wejściowego grafu G=(V,E) będziemy budować graf nad zbiorem jego wierzchołków V(G) powiększonym o superźródło s i superujście t. Niech d(v) oznacza różnicę między liczbą krawędzi wychodzących z v a liczbą krawędzi wchodzących do v (w wejściowym grafie).
Wstawiamy następujące krawędzie:W tym grafie szukamy maksymalnego przepływu o minimalnym koszcie między s a t. Nieskończone przepustowości gwarantują, że zawsze znajdziemy przepływ, który nasyca zarówno krawędzie wychodzące z s, jak i te wchodzące do t (nasycenie jednych jest równoważne nasyceniu drugich). Używane przez nas algorytmy dla sieci o przepustowościach całkowitoliczbowych znajdują całkowitoliczbowe przepływy.
Aby otrzymać wynik, patrzymy na przepływy po krawędziach między wierzchołkami w V(G) i dla każdej krawędzi jej krotność w wynikowym multizbiorze jest wyznaczona przez przepływ po tej krawędzi. Wynik jest poprawny (z warunków na przepływ) oraz optymalny (bo z dowolnego rozwiązania da się uzyskać przepływ).
Możemy ograniczyć wartość maksymalnego przepływu w sieci przez O(|E|) (istnieją również sieci, w których ta wartość jest osiągana). Używamy algorytmu do znajdowania maksymalnego przepływu o minimalnym koszcie (O(|f*|(n2 + m))), zatem cały algorytm działa w czasie O(|E||V|2).
Inne możliwe podejście jest takie, że najpierw znajdujemy najkrótszą ścieżkę między każdą parą wierzchołków, względem wagi w, a następnie korzystamy z konstrukcji podobnej do powyższej, przy czym wstawiamy nieco inne krawędzie (różnica występuje w 3. podpunkcie):
W efekcie dostajemy sieć bez cykli. Gdy użyjemy algorytmu z wykładu, ostateczna złożoność pozostaje taka sama.
Pokażę, że ten problem jest NP-trudny.
Zredukuję do tego problemu problem cyklu Hamiltona w grafie skierowanym. Dla podanego grafu G=(V,E), tworzymy instancję naszego problemu. Składa się ona z grafu o |V| wierzchołkach, który nie zawiera krawędzi, oraz funkcji w danej:
Jasne jest, że do wyniku musimy wziąć co najmniej n krawędzi, zatem minimalna waga to n. Jeśli dostaliśmy rozwiązanie o takim koszcie, to odpowiada ono cyklowi Hamiltona w oryginalnym grafie (graf Eulerowski ma co najmniej n krawędzi, zatem użyliśmy jedynie krawędzi z oryginalnego grafu). Z drugiej strony, cykl Hamiltona wprost wyznacza rozwiązanie o wadze n.
Pozostaje pokazać, że redukcja działa w czasie wielomianowym. W zasadzie jest to jasne, przy czym zakładamy tu, że reprezentacja grafu na |V| wierzchołkach wymaga co najmniej |V| bitów informacji.
Gdyby istniało rozwiązanie wielomianowe dla tego problemu, to istniałoby również rozwiązanie wielomianowe dla dowolnego problemu z klasy NP. Jest to sprzeczne z założeniem , że P ≠ NP, więc rozwiązanie wielomianowe nie może istnieć.
Na początku każdy okręg dzielimy na dwa łuki, które stanowią górną i dolną połówkę okręgu. Dla tego zbioru łuków używamy algorytmu analogicznego do algorytmu znajdowania wszystkich przecięć w podanym zbiorze odcinków. W miotle trzymamy zbiór łuków, które aktualnie ją przecinają, posortowanych względem współrzędnej przecięcia. Kolejność łuków na miotle zmienia się jedynie w momencie przecięcia dwóch łuków. Trzeba jednak pamiętać, że gdy łuki są styczne, przecięcie nie doprowadzi do zamiany ich kolejności.