Czy istnieje skuteczny algorytm dla tego problemu pokrycia cyklu wierzchołków?

Próbowałem znaleźć algorytm do znalezienia maksymalnego pokrycia cyklu wierzchołków ukierunkowanego wykresu - to znaczy zestawu rozłącznych cykli, które zawierają wszystkie wierzchołki w , z jak największą liczbą cykli (nie bierzemy pod uwagę poszczególne cykle wierzchołków tutaj). Wiem, że problem znalezienia minimalnego pokrycia cyklu wierzchołków, a także znalezienia pokrycia cyklu wierzchołków o dokładnie cyklach jest NP-zupełny. Ale co z maksymalnym przypadkiem?$G$$G$$k$

Chociaż ogólnie znajdę odpowiedź na to interesujące, wykresy, których chcę użyć, są w rzeczywistości dość ograniczone ze względu na ich konstrukcję, więc może nawet jeśli problem jest NP-zupełny, może istnieć rozwiązanie wielomianowe dla tych konkretnych przypadków.

Mamy listę liczb całkowitych , elementów i użyjemy , elementów do odniesienia do po posortowaniu. Jako przykład:l i S s i$L$$l_i$$S$$s_i$$L$

Wierzchołki wykresu będą identyfikowane za pomocą par takich, że l_i = n i s_i \ neq n . Wykres ma skierowaną krawędź (n, i) \ rightarrow (m, j) wtedy i tylko wtedy, gdy s_j = n . (Cykl na tym wykresie odpowiada zestawowi wartości, które można cyklicznie permutować, tak aby wylądowały w posortowanej pozycji).$(n, i)$$l_i = n$$s_i \neq n$$(n, i) \rightarrow (m, j)$$s_j = n$

Powyższy przykład dałby następujący wykres (przy użyciu wskaźników opartych na 1):

Jedną z rzeczy, która nie działa, jest chciwe podejście polegające na wielokrotnym usuwaniu najmniejszego cyklu (jak pokazuje ten przykład).

Zauważ, że ten problem jest (jeśli nie popełniłem żadnych błędów) równoznaczny z pytaniem, ile swapów potrzebujesz do posortowania danej listy. (Które przede wszystkim zainspirowało spojrzenie na ten problem).

Po kilku wskazówkach z odpowiedzi Juho i nieco dokładniejszym przejrzeniu literatury natknąłem się na problem przydziału, który wydaje się bardzo blisko powiązany. Jednak problem przypisania jest sformułowany w postaci ważonego wykresu dwudzielnego i do tej pory nie byłem w stanie znaleźć sposobu wyboru krawędzi i ciężarów, aby zredukować do niego ten problem. Gdybyśmy chcieli sformułować tutaj problem w zakresie minimalizacji funkcji wagi, wówczas intuicyjne podejście polegałoby na stwierdzeniu, że waga każdego cyklu wynosi gdzieto liczba krawędzi (lub wierzchołków) w cyklu. (Oczywiście jest to równoważne z ustawieniem ciężaru na$|C|-1$$|C|$$-1$.) Oznacza to, że ciężar zależy od wielkości cyklu, a nie od poszczególnych krawędzi, które zawiera. Ale może to daje komuś inny pomysł na zmniejszenie problemu.

Wydaje się również, że ograniczenie rozmiaru cykli powoduje, że problem APX jest trudny w przypadku ogólnych wykresów. Nie musi to wcale oznaczać, że to samo dotyczy zadania polegającego na maksymalizacji liczby cykli, ani konkretnych analizowanych tutaj wykresów, ale wydaje się, że jest wystarczająco blisko powiązane, że może być ważne.

Podsumowując: Czy dla wykresów zbudowanych z powyższego procesu można znaleźć maksymalne pokrycie cyklu z rozłącznym wierzchołkiem?

Na marginesie, byłbym również zainteresowany tym, czy maksymalne rozłączne pokrycie cyklu wierzchołka ma również skuteczne rozwiązanie dla dowolnych wykresów, które dopuszczają co najmniej jedno pokrycie cyklu (które prawdopodobnie wypadnie jako odpowiedź na główne pytanie), czy też samo określenie liczby cykli w maksymalnym pokryciu (w przeciwieństwie do rzeczywistych krawędzi zawartych w każdym z nich) czyni problem jeszcze prostszym. Z przyjemnością zamieszczam je jako osobne pytania, jeśli ludzie uważają, że same zasługują na pełne odpowiedzi.

Niech pokrycie cyklu ukierunkowanego wykresu będzie zbiorem cykli rozłącznych wierzchołków, tak aby każdy wierzchołek był dokładnie w jednym cyklu. Więc jeśli dobrze cię rozumiem, biorąc pod uwagę ukierunkowany wykres , potrzebujesz maksymalnego pokrycia cyklu, w którym każdy cykl ma długość co najmniej (być może dla lub co najmniej ). Pokrywa cykl gdzie każdy cykl ma długość co najmniej nazywamy pokrywa -cycle .$G$$k$$k=2$$k=3$ $k$$k$

Decyzja, czy wykrój ma 2-cyklową osłonę, jest możliwa do rozwiązania w czasie wielomianowym. Problem decydowania o tym, czy ma pokrycie 3-cyklowe, jest NP-zupełny. Odpowiadający problem optymalizacji (tj. Znalezienie 3-cyklowej osłony o maksymalnej masie) jest zakończony APX i ma algorytm aproksymacji (dla dowolnego ). Dobrą wiadomością jest to, że można obliczyć maksymalną masę 2-cyklowego pokrycia w czasie wielomianowym (pod warunkiem, że wagi krawędzi są nieujemne).$G$$G$$((3/5)-\epsilon)$$\epsilon > 0$

Aby uzyskać szczegółowe informacje i dowody powyższych twierdzeń, patrz [1].

[1] Bläser, Markus i Bodo Manthey. „Dwa algorytmy aproksymacyjne dla okładek 3-cyklowych”. Algorytmy aproksymacyjne dla optymalizacji kombinatorycznej. Springer Berlin Heidelberg, 2002. 40-50.