Anzahl der Eckpunkte, die in allen maximalen Übereinstimmungen vorhanden sind

Bei einem gegebenen Graphen müssen wir die Kardinalität der größten Menge von Scheitelpunkten finden, so dass jeder von ihnen in jeder maximal möglichen Übereinstimmung vorhanden ist. $G$

Gibt es neben dem offensichtlichen eine Lösung, jeden Scheitelpunkt zu entfernen und die maximale Übereinstimmung zu finden, um zu sehen, dass er reduziert wird?

graph-theory graph-algorithms Hououin Kyouma
quelle

Ich verstehe nicht, wie das, was Sie vorgeschlagen haben, überhaupt eine Lösung ist. (Betrachten Sie ein Dreieck.)

$\:$

$\hspace{1.4 in}$

@ RickyDemer zuerst finden wir maximale Übereinstimmung in der gesamten Grafik. Dann entfernen wir einen Scheitelpunkt und finden erneut die maximale Übereinstimmung. Wenn der Unterschied 1 ist, können wir sagen, dass dieser Eckpunkt in allen maximalen Übereinstimmungen vorhanden ist.

Evil999man

Sollte "maximale Übereinstimmung finden" durch "maximale Übereinstimmung finden" oder "alle maximalen Übereinstimmungen finden" ersetzt werden?

$\;$

Ich denke, es sollte mit der Größe der maximalen Übereinstimmung ersetzt werden.

Evil999man

@Awesome ist richtig. Ich werde meine Frage bearbeiten.

Hououin Kyouma

Antworten:

Ich denke, Sie wollen die Edmonds-Gallai-Zerlegung Ihres Graphen, die in Zeit berechnet werden kann (siehe diese Hinweise ). $O(n^3)$

Thomas Kalinowski
quelle

Ich brauche nur Größe, nicht die Eckpunkte selbst. Kann das in O (n ^ 2) gemacht werden? Und danke für die Zeitung

Hououin Kyouma

Ist Ihr Graph zweiteilig? Angenommen, eine Seite der Bipartition ist links und die andere rechts. Finden Sie eine maximale Übereinstimmung und richten Sie alle übereinstimmenden Kanten von links nach rechts und alle nicht übereinstimmenden Kanten von rechts nach links aus. Dann kann ein Eckpunkt aus einer maximalen Übereinstimmung nur dann weggelassen werden, wenn eine der drei folgenden (sich gegenseitig ausschließenden) Bedingungen zutrifft: $v$

ist bereits unerreicht $v$
kann von einem nicht angepassten Scheitelpunkt auf der Seite der Bipartition im resultierenden Digraphen erreicht werden $v$
$v$

Wenn Sie zwei Breitensuchen oder Tiefensuchen ausführen, um die Teile des Diagramms zu finden, die von nicht übereinstimmenden Scheitelpunkten aus erreichbar sind, und um die Teile zu finden, die nicht übereinstimmende Scheitelpunkte erreichen können, können Sie die wesentlichen Scheitelpunkte in linearer Zeit finden habe schon das passende.

Möglicherweise funktioniert so etwas auch für den nicht-bipartiten Fall, bei dem eine Suche nach blütenkontrahierenden Alternativpfaden verwendet wird, aber die Details werden komplizierter.

David Eppstein
quelle

Ich bin gespannt, wie Sie das in einem allgemeinen Diagramm machen würden. Kannst du es erklären?

Evil999man

Wenn ich es bereits im Detail ausgearbeitet hätte, hätte ich es in meine Antwort aufgenommen. Grundsätzlich möchten Sie jedoch nur die Scheitelpunkte finden, die durch abwechselnde Pfade von unerreichten Scheitelpunkten erreicht werden können, da diese möglicherweise nicht übereinstimmen. Die Suche nach alternierenden Pfaden sollte so ziemlich die gleiche sein, die Sie verwenden, um die Übereinstimmung überhaupt zu finden.

David Eppstein

Entschuldigung für den späten Kommentar. Mein Diagramm ist allgemein. Ich werde versuchen, die Methode zu überdenken

Hououin Kyouma