Jak generować wykresy ze znaną optymalną osłoną wierzchołków

Szukam sposobu generowania wykresów, aby znana była optymalna osłona wierzchołków. Nie ma ograniczeń co do liczby węzłów lub krawędzi, tylko to, że wykres jest całkowicie połączony.

chodzi o wygenerowanie wykresu, który nie jest łatwy do znalezienia optymalnej osłony wierzchołków, aby móc przetestować na niej różne heurystyki

Znalazłem artykuł Arthur, J. i Frendeway, J. Generowanie problemów podróżujących sprzedawców ze znanymi optymalnymi trasami, The Journal of the Operational Research Society, t. 39, nr 2 (luty, 1988), str. 153-159 do generowania TSP ze znanym optymalnym, niestety nie mogę uzyskać do niego dostępu.

Czy istnieje znany algorytm?

ds.algorithms graph-theory graph-algorithms

— AndresQ
źródło

„Nie ma ograniczeń co do liczby węzłów lub krawędzi, tylko to, że wykres jest całkowicie połączony”. Potrzebujesz więcej ograniczeń niż to. W przeciwnym razie generuję zestaw kompletnych wykresów i znam optymalne pokrycie wierzchołków dla każdego z nich.

— Tyson Williams,

M

$M$

e \in M

$e \in M$

C

$C$

C

$C$

C

$C$

K_{3}

$K_3$

Przypuszczam, że „wygenerowanie losowego dwustronnego wykresu i obliczenie jego osłony wierzchołka” nie liczy się jako przydatna odpowiedź ...

— David Eppstein

istnieje wiele strategii tworzenia „twardych” instancji SAT, a także repozytoriów zarchiwizowanych „twardych” instancji, jeśli chcesz iść tą drogą - tj. konwertować instancję SAT na pokrycie wierzchołków. jest też wiele badań dotyczących SAT z empirycznego pov, co naturalnie przekłada się na wszystkie inne problemy NP całkowite, np. punkt przejścia itp. wiele

— odwołuje się

Nawet bardziej ogólnie niż wielomianowa czasowa rozwiązalność pokrycia wierzchołków na grafach Koninga, jak zauważył David, następujący obszar jest znany z obszaru sparametryzowanej złożoności: istnieje stała c taka, że dla każdej stałej liczby całkowitej k występuje O (n ^ c) algorytm czasowy sprawdzający, czy wykres ma pokrycie wierzchołków, które przekracza maksymalny rozmiar dopasowania o najwyżej k. Wykresy Koniga są szczególnym przypadkiem, gdy k = 0.

— Bart Jansen,

Odpowiedzi:

Rozwinięcie komentarza vzn w odpowiedź: Standardowa redukcja z CNF-SAT do pokrycia wierzchołków jest dość łatwa: utwórz wierzchołek dla każdego terminu (zmienna lub jego negacja), połącz każdą zmienną z negacją krawędzią, utwórz klikę dla każdej klauzuli i połącz każdy wierzchołek kliki z wierzchołkiem dla jednego z warunków w klauzuli. Jeśli zaczniesz od problemu satysfakcji ze znanym zadawalającym zadaniem, da ci to problem z pokrywą wierzchołków ze znanym optymalnym rozwiązaniem (wybierz termin wierzchołki podany w zadaniu, a w każdej klauzuli kliki wybierz wszystkie oprócz jednego wierzchołka, tak aby klauzula wierzchołek, który nie jest wybrany, sąsiaduje z wybranym wierzchołkiem).

Więc teraz musisz znaleźć problemy z zadowalaniem, które mają znane zadowalające zadanie, ale gdzie rozwiązanie jest trudne do znalezienia. Istnieje wiele znanych sposobów generowania trudnych problemów satysfakcji (np. Generowanie losowych instancji k-SAT zbliżonych do progu satysfakcji), ale dodatkowy wymóg znajomości satysfakcjonującego przypisania ogranicza możliwości. Jedną z rzeczy, które możesz tutaj zrobić, jest przejście przez inny poziom redukcji, od trudnego kryptograficznie problemu, takiego jak faktoryzacja. To znaczy wybierz dwie duże liczby pierwsze p i q, ustaw obwód boolowski do mnożenia p i q jako liczby binarne i przetłumacz go na formułę CNF, w której dla każdego wejścia (p i q) i dla każdej wartości pośredniej jest zmienna drut w obwodzie, klauzula dla każdego wyjścia, zmuszająca go do uzyskania właściwej wartości, oraz klauzula dla każdej bramki wymuszająca spójność między wejściami i wyjściami bramki. Następnie przetłumacz tę formułę CNF na osłonę wierzchołków.

Aby uzyskać prostszą strategię, najpierw wybierz satysfakcjonujące przypisanie do formuły 3CNF, a następnie generuj losowo klauzule, zachowując tylko te klauzule, które są zgodne z przypisaniem, a następnie przekonwertuj na pokrycie wierzchołków. Jeśli klauzule mają jednolite prawdopodobieństwo, będzie to podatne na heurystykę opartą na stopniach (termin wierzchołki pasujące do wybranego przypisania będzie miał niższy stopień niż termin wierzchołki, które nie spełniają), ale tej wady można uniknąć poprzez dostosowanie prawdopodobieństwa klauzul zgodnie z tym, ile warunków klauzuli zgadza się z wybranym zleceniem. Prawdopodobnie jest to podatne na atak wielomianowy w czasie, ale może nie być to naturalne dla pokrycia wierzchołków, więc może stanowić dobry zestaw instancji testowych, mimo że nie ma dużej gwarancji twardości.

— David Eppstein
źródło

\cap

$\cap$

najbliższym refem, który znalazłem było ... W trudnych przypadkach przybliżonego pokrycia wierzchołków przez Sundara Vishwanathana. nie widziałem referencji za sprawdzanie trudnych przypadków konkretnego problemu.

jak w moim komentarzu, istnieje wiele badań nad tym odpowiednim podejściem do SAT, które można zredukować do pokrycia wierzchołków.

Jeśli chodzi o komentarz DE, pomysł generowania przypadkowych instancji i wybierania takich instancji, które są trudne dla standardowego algorytmu, wydaje mi się całkowicie rozsądny, szczególnie przy empirycznym / eksperymentalnym podejściu badawczym [1], jest to standardowa procedura operacyjna dla podobnych badań nad SAT punkt przejścia. [2]

który, nawiasem mówiąc, ma coś do powiedzenia, gdzie „twardy” region jest dla dowolnego innego problemu NP pełnego [3,4,5], który odnosi się mniej więcej do punktu krytycznego w „gęstości” 1s w przypadkowych przypadkach określonych w systemie binarnym. dla pokrycia wierzchołków prawdopodobnie odpowiada to gęstości krawędzi.

zauważ, że udowodnienie, że można zbudować zestaw twardych instancji i tylko twardych instancji, jest w zasadzie równoważne problemowi P vs NP. bardziej formalna analiza tej równoważności znajduje się w pracy Razborov / Rudich Natural Proofs.

[1] algorytmy eksperymentalne

[2] Badania przejścia fazowego SAT

[3] Przejścia fazowe w trudnych problemach NP

[4] Przejścia fazowe w problemach NP-zupełnych: wyzwanie dla prawdopodobieństwa, kombinatoryki i informatyki autorstwa Moore'a

[5] Zachowanie przemiany fazowej przez Walsha

— vzn
źródło