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$ $l_i$ $S$ $s_i$ $L$

L. = (1, 3), 2), 5, 0, 7, 4, 2), 6, 0, 8, 1) S. = (0, 0, 1, 1, 2), 2), 3), 4, 5, 6, 7, 8)

$L = (1, 3, 2, 5, 0, 7, 4, 2, 6, 0, 8, 1)\\ S = (0, 0, 1, 1, 2, 2, 3, 4, 5, 6, 7, 8)$

Wierzchołki wykresu będą identyfikowane za pomocą par takich, że i . Wykres ma skierowaną krawędź wtedy i tylko wtedy, gdy . (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.

graph-theory algorithms

— Martin Ender
źródło

Czy spojrzałeś na literaturę CS dotyczącą wymiany nerek? Problem wydaje się powiązany, więc zastanawiam się, czy można zastosować jakąkolwiek z dostępnych metod. Może to być jednak ślepy zaułek ...

— DW

@DW Nie wiedziałem (nie wiedziałem, że to jest coś). Zobaczę, co mogę znaleźć, dzięki.

— Martin Ender

problem jest rzeczywiście podobny do wymiany nerki, którą rzeczywiście badano na podstawie teoretycznego pow. np. niniejszy artykuł Roughgarden wyjaśnia, że małe cykle są preferowane z prawie oczywistych powodów (p3); rozmiary cykli oznaczają „równoczesne operacje”, a mniejsze zmniejszają ryzyko wykonania wszystkich operacji z powikłaniami lub zmianami umysłu dawców itp.

— dniu

@AustinMohr Wierzę, że wykresy uzyskane z konstrukcji, którą opisuję, zawsze będą rozkładały się na cykle (a ponadto, bez względu na to, który cykl usuniesz, reszta nadal będzie rozkładalna na cykle). Jeśli chcesz odnieść się również do ogólnych wykresów, załóż, że istnieje co najmniej jedna pełna okładka.

— Martin Ender,

@ MartinBüttner Czy w twoim konkretnym przypadku, jeśli wszystkie elementy listy są różne, czy twój problem byłby równoznaczny ze znalezieniem (unikalnego) cyklu rozkładu permutacji ?

— mhum

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.

— Juho
źródło

Ciekawe, postaram się śledzić odniesienia z tego artykułu. Dzięki. (Musiałem coś źle odczytać, gdy pomyślałem, że okładki z cyklu K są okładkami z dokładnie takimi cyklami. A może to inna definicja używana gdzie indziej.)

— Martin Ender

@ MartinBüttner Przy okazji, prawdopodobnie zechcesz zobaczyć doktorat Bläser tutaj . (Jest w języku niemieckim, ale prawdopodobnie nie będziesz miał z tym problemu :-)). Powinien on obejmować szczegóły faktycznego obliczania 2-cyklowego ubezpieczenia o maksymalnej wadze.

— Juho

| V | - n

$|V|-n$

n

$n$

Myśląc o tym trochę więcej, nie jestem pewien, czy rzeczywiście można sformułować problem pod względem wag. Przy równej wadze wszystkie pokrowce na rowery mają taką samą wagę. Mój „koszt” cyklu to w rzeczywistości jego długość minus 1. Dlatego chcę jak największej liczby cykli. Jeśli można to sformułować w kategoriach wag, ogranicza się to do problemu przypisania, ale jeśli nie, to chyba muszę szukać dalej.

— Martin Ender