Wie erstelle ich einen Zufallsgraphen ohne Hamilton-Zyklus?

Die Klasse A bezeichne alle Graphen der Größe , die einen Hamilton-Zyklus haben. Es ist einfach, einen zufälligen Graphen aus dieser Klasse zu erstellen - isolierte Knoten nehmen, einen zufälligen Hamilton-Zyklus hinzufügen und dann Kanten zufällig hinzufügen. $n$ $n$

Die Klasse B bezeichne alle Graphen der Größe die keinen Hamilton-Zyklus haben. Wie können wir einen zufälligen Graphen aus dieser Klasse auswählen? (oder etwas in der Nähe tun) $n$

ds.algorithms graph-theory Jagadisch
quelle

Wie ist es klar, dass die erste Prozedur Graphen gleichmäßig zufällig erzeugt? Es ist klar, dass immer Hamilton-Graphen erstellt werden. Da Sie jedoch später nach dem Zufallsprinzip Kanten hinzufügen, führen Sie möglicherweise mehr Hamilton-Zyklen ein, sodass einige Graphen häufiger als andere angezeigt werden.

Robin Kothari

Dies ist richtig, aber eine einheitliche Verteilung wurde nicht angefordert (falls dies impliziert sein sollte).

Raphael

Ja, Uniformität ist mir egal. Ich möchte jedem Graphen in der Familie der Nicht-Hamilton-Graphen eine Chance geben, ausgewählt zu werden. Das Problem mit der einheitlichen Abtastung ist recht einfach: AFAIK, wir wissen nicht, wie einheitlich eine Familie von Graphen der Größe n abgetastet wird, geschweige denn solche mit Hamilton-Zyklen.

Jagadish

Antworten:

Dies ist unmöglich (es sei denn, NP = coNP), da dies insbesondere eine Polyzeitfunktion impliziert, deren Bereich die Nicht-Hamilton-Graphen sind (die Funktion geht von der Zufallszeichenfolge zum Ausgabegraphen), was wiederum einen NP-Beweis impliziert von Nicht-Hamiltonianität (um zu beweisen, dass G keinen Hamilton-Schaltkreis hat, zeigen Sie x, das diesem zugeordnet ist.)

Noam
quelle

Sie gehen davon aus, dass sich eine solche Funktion auf die Klasse der Nicht-Hamilton-Graphen bezieht. Dies ist nur der Fall, wenn die Verteilung gleichmäßig sein soll. Siehe auch Aarons Kommentar unten: cstheory.stackexchange.com/questions/562/…

Ohad Kammar

Dies setzt nichts über die Wahrscheinlichkeiten der Auswahl der einzelnen Graphen voraus (so dass es einheitlich ist), nur dass die Graphen, die von den Algorithmen ausgegeben werden können, genau die Nicht-Hamilton-Graphen sind (auf). Wenn Sie Fehler auf beiden Seiten zulassen, ist dies in der Tat möglich.

Noam

Ich stimme zu, es kommt nicht auf die Gleichmäßigkeit der Verteilung an, sondern auf die Tatsache, dass alle Nicht-Hamilton-Graphen eine Wahrscheinlichkeit ungleich Null haben. Wenn auch nur einer von ihnen eine Wahrscheinlichkeit von Null hat, gilt Ihr Beweis nicht (ohne weitere Kenntnisse über die Unterstützung der Distribution).

Ohad Kammar

@Ohad: Wenn einer von ihnen ausgelassen wird, können Sie diesen einfach zu einer Nachschlagetabelle hinzufügen. Ich denke, die Probleme beginnen erst, wenn Sie einen positiven Bruchteil davon verpassen, aber dann nicht einheitlich abtasten.

Emil

Wenn Ihr Algorithmus eine gleichmäßige Verteilung auf den Nicht-Hamilton-Graphen mit der Wahrscheinlichkeit

und einem Hamilton-Graphen mit der Wahrscheinlichkeit

und

als Eingabegröße für

, sollten Sie in der Lage sein, diesen Algorithmus mit zu kombinieren zufällige Hash-Funktionen, um einen interaktiven Konstant-Runden-Beweis für Nicht-Hamiltonizität zu finden. Dies würde bedeuten, dass die Polynom-Hierarchie zusammenbricht

1 - ϵ

$1-\epsilon$

ϵ

$\epsilon$

ϵ \to 0

$\epsilon \rightarrow 0$

\infty

$\infty$

Peter Shor

Bollobas, Fenner und Frieze (http://portal.acm.org/citation.cfm?id=22145.22193) geben einen polynomiellen Zeitalgorithmus zum Auffinden von Hamilton-Zyklen in Zufallsgraphen an, dessen Fehlerrate asymptotisch gegen 0 tendiert des Graphen. Wenn Sie n Scheitelpunktgraphen erzeugen möchten, die nicht Hamiltonsch sind, können Sie einen Zufallsgraphen auswählen $G_{n,m}$ $m$ $n$

$n$

Aaron Roth
quelle

Dies ist eine gute Idee, obwohl wir den gesamten probabilistischen Algorithmus zum Finden des Ham-Zyklus überspringen können. Die Frage stellt nicht die Frage, ob das Stichprobenverfahren in der erwarteten Mehrfachzeit oder irgendetwas ausgeführt wird. Erstellen Sie also ein zufälliges Diagramm aus Ihrer bevorzugten Verteilung, bestimmen Sie, ob es sich um ein Hamilton-Diagramm mit einem genauen Algorithmus handelt, und verwerfen Sie es, und wiederholen Sie den Vorgang. Wenn die verwendete Verteilung die gleichmäßige Verteilung über alle beschrifteten Graphen war, wird dies tatsächlich jeden nicht mit Hamilton bezeichneten Graphen mit gleichmäßiger Wahrscheinlichkeit erzeugen.

JimN 29.11.10

Die erste Aufgabe ist einfach, da Hamilton-Graphen leicht zu überprüfen sind. Es ist jedoch kein kurzer Beweis bekannt, der effizient verifiziert werden kann, um zu bezeugen, dass ein gegebener Graph kein Hamilton-Graph ist.

Mohammad Al-Turkistany
quelle

Ich denke, die Antwort von turkistany wirft eine interessante Frage auf. Ist es im Allgemeinen möglich, aus einer Sprache, die co-NP-complete ist, eine einheitliche Probe zu erstellen?

Suresh Venkat

.... und Noam verneint das.

Suresh Venkat