Jak stworzyć losowy wykres, który nie ma cyklu hamiltonowskiego?

Niech klasa A oznacza wszystkie wykresy wielkości które mają cykl hamiltonowski. Z tej klasy łatwo jest utworzyć losowy wykres - weź izolowanych węzłów, dodaj losowy cykl hamiltonowski, a następnie losowo dodaj krawędzie. $n$ $n$

Niech klasa B oznacza wszystkie wykresy wielkości które nie mają cyklu hamiltonowskiego. Jak możemy wybrać losowy wykres z tej klasy? (lub zrób coś podobnego) $n$

ds.algorithms graph-theory Jagadish
źródło

Jak jasne jest, że pierwsza procedura generuje losowo wykresy jednolicie? Oczywiste jest, że zawsze tworzy wykresy Hamiltona, ale ponieważ później dodajesz krawędzie losowo, możesz wprowadzić więcej cykli Hamiltona, powodując, że niektóre wykresy pojawiają się częściej niż inne.

Robin Kothari,

Zgadza się, ale nie zażądano jednolitego podziału (jeśli może to sugerować).

Raphael,

Tak, nie dbam o jednolitość. Chciałbym dać szansę każdemu wykresowi z rodziny grafów niehamiltonowskich. Problem z jednolitym próbkowaniem jest dość prosty: AFAIK, nie wiemy, jak próbkować równomiernie z rodziny wykresów wielkości n, nie mówiąc już o tych z cyklami hamiltonowskimi.

Jagadish,

Odpowiedzi:

Jest to niemożliwe (chyba że NP = coNP), ponieważ w szczególności implikuje to funkcję wielozakresową, której zakresem są wykresy niehamiltonowskie (funkcja przechodzi od losowego ciągu do grafu wyjściowego), co z kolei implikuje dowód NP nie Hamiltonianizmu (aby udowodnić, że G nie ma obwodu hamiltonowskiego, pokaż x, który go odwzorowuje).

Noam
źródło

Zakładasz, że taka funkcja należy do klasy grafów innych niż hamiltonowskie. Dzieje się tak tylko wtedy, gdy chcemy, aby rozkład był jednolity. Zobacz także komentarz Aarona poniżej: cstheory.stackexchange.com/questions/562/…

Ohad Kammar

Nie zakłada to niczego o prawdopodobieństwach wyboru każdego wykresu (tak, że jest on jednolity), tylko że wykresy, które mogą być generowane przez algorytmy, są dokładnie tymi, które nie są hamiltonowskie (na). Jeśli dopuścisz błąd po obu stronach, może to być możliwe.

Noam

Zgadzam się, że nie liczy się jednolitość rozkładu, ale fakt, że wszystkie wykresy inne niż hamiltonowskie mają niezerowe prawdopodobieństwo. Jeśli choć jedno z nich ma zerowe prawdopodobieństwo, dowód nie ma zastosowania (bez dodatkowej wiedzy na temat obsługi dystrybucji).

Ohad Kammar

@Ohad: jeśli jeden z nich zostanie pominięty, możesz po prostu dodać to do tabeli przeglądowej. Myślę, że problemy zaczynają się tylko wtedy, gdy przegapisz ich pozytywną część, ale wtedy nie próbujesz jednolicie.

Emil

1 - ϵ

$1-\epsilon$

ϵ

$\epsilon$

ϵ \to 0

$\epsilon \rightarrow 0$

\infty

$\infty$

$G_{n,m}$ $m$ $n$

$n$

Aaron Roth
źródło

To dobry pomysł, chociaż możemy pominąć cały algorytm probabilistyczny do znalezienia cyklu Ham. Pytanie nie wymaga, aby procedura próbkowania przebiegała w oczekiwanym czasie polytime lub cokolwiek innego. Utwórz więc losowy wykres ze swojej ulubionej dystrybucji, określ, czy jest to Hamiltonian z jakimś dokładnym algorytmem, a jeśli jest to Hamiltonian, odrzuć go i powtórz proces. Jeśli zastosowanym rozkładem był rozkład równomierny na wszystkich znakowanych wykresach, faktycznie wygeneruje każdy wykres nieoznaczony Hamiltonianem z jednakowym prawdopodobieństwem.

JimN

Pierwsze zadanie jest łatwe, ponieważ wykresy Hamiltona są łatwe do zweryfikowania. Jednak nie jest znany krótki dowód, który można skutecznie zweryfikować, aby stwierdzić, że dany wykres nie jest hamiltonowski.

Mohammad Al-Turkistany
źródło

Myślę, że odpowiedź turkistany rodzi interesujące pytanie. Zasadniczo czy możliwe jest jednolite próbkowanie z języka, który jest co-NP-complete?

Suresh Venkat

.... i Noam odpowiada na to przecząco.

Suresh Venkat,