Gibt es einen Algorithmus, der die verbotenen Minderjährigen findet?

Das Robertson-Seymour-Theorem besagt, dass jede kleinere geschlossene Familie $\mathcal G$ von Graphen durch endlich viele verbotene Minderjährige charakterisiert werden kann.

Gibt es einen Algorithmus, der für einen Eingang $\mathcal G$ die verbotenen Minderjährigen ausgibt, oder ist dies unentscheidbar?

Offensichtlich könnte die Antwort davon abhängen, wie $\mathcal G$ in der Eingabe beschrieben wird. Zum Beispiel, wenn $\mathcal G$ von einem gegeben ist $M_\mathcal G$ , die Mitgliedschaft entscheiden kann, können wir nicht einmal entscheiden , ob $M_\mathcal G$ jemals etwas ablehnt. Wenn $\mathcal G$ von endlich vielen verbotenen Minderjährigen gegeben wird - nun, das ist es, wonach wir suchen. Ich wäre gespannt auf die Antwort, wenn $M_\mathcal G$ garantiert in einem festgelegten Zeitraum in auf einem $G$ stoppt . Ich interessiere mich auch für verwandte Ergebnisse, bei denen nachgewiesen wird, dass mit einem anderen Zertifikat (wie im Fall von geringfügig geschlossen ist $|G|$ $\mathcal G$ $TFNP$ oderFALSCHER BEWEIS).

Update: Die erste Version meiner Frage erwies sich als recht einfach, basierend auf den Ideen von Marzio und Kimpel. Betrachten Sie die folgende Konstruktion. $M_\mathcal G$ akzeptiert einen Graphen auf $n$ Eckpunkten genau dann, wenn $M$ nicht in $n$ Schritten anhält. Dies ist geringfügig geschlossen und die Laufzeit hängt nur von $|G|$ .

graph-theory decidability graph-minor domotorp
quelle

G

$\mathcal G$

M_{G}

$M_\mathcal G$

M

$M$

M_{G} (G_{x})

$M_\mathcal G( G_x )$

M

$M$

x

$x$

(G_{1}, G_{2}, . . .

$(G_1,G_2,...$

M_{G} (G_{x})

$M_\mathcal G( G_x )$

G

$\mathcal G$

Marzio De Biasi

M_{G} (G_{x})

$M_\mathcal G( G_x )$

G_{i}, i \leq x

$G_i, i \leq x$

M

$M$

i

$i$

G_{i}

$G_i$

G_{x}

$G_x$

M_{G}

$M_\mathcal G$

n

$n$

M

$M$

n

$n$

| G |

$|G|$

M

$M$

2

$2$

3

$3$

@domotorp Da Ihre Konstruktion funktioniert (wenn ich mich nicht irre) und eine Ihrer Fragen beantwortet (und Marzio De Biasi und ich versucht haben, eine so einfache Konstruktion ohne Erfolg zu entwickeln), sollten Sie Ihre Konstruktion in eine verwandeln richtige Antwort. Sie können es zu einem Community-Wiki machen, wenn Sie sich nicht sicher sind, ob Sie Ihre eigene Frage beantworten sollen. Alternativ können Sie Ihre Frage bearbeiten und dort die Antwort hinzufügen.

Thomas Klimpel

Die Antwort von Mamadou Moustapha Kanté (der unter der Aufsicht von Bruno Courcelle promovierte) auf eine ähnliche Frage zitiert eine Anmerkung zur Berechenbarkeit graphgrafischer Obstruktionssätze für monadische Ideale zweiter Ordnung (1997) von B. Courcelle, R. Downey und M. Fellows für ein nicht berechenbares Ergebnis (für MSOL-definierbare Graphklassen, dh Klassen, die durch eine monadische Formel zweiter Ordnung definiert sind) und die Hindernisse einer geringfügig geschlossenen Menge von Graphen, die durch eine kontextfreie Grammatik (1998) von B definiert wurden Courcelle und G. Sénizergues für ein Berechenbarkeitsergebnis (für HR-definierbare Diagrammklassen, dh Klassen, die durch eine Hyperedge-Ersatz-Grammatik definiert sind).

Der entscheidende Unterschied zwischen dem berechenbaren und dem nicht berechenbaren Fall besteht darin, dass (geringfügig geschlossene) HR-definierbare Diagrammklassen eine begrenzte Baumbreite haben, während (geringfügig geschlossene) MSOL-definierbare Diagrammklassen keine begrenzte Baumbreite haben müssen. Wenn eine (geringfügig geschlossene) MSOL-definierbare Diagrammklasse die Baumbreite begrenzt hat, ist sie auch HR-definierbar.

Die Baumbreite scheint wirklich der entscheidende Teil für die Trennung der berechenbaren von den nicht berechenbaren Fällen zu sein. Ein anderes bekanntes Ergebnis (von M. Fellows und M􏰊.􏰊 Langston) besagt grundsätzlich, dass, wenn eine Grenze für die maximale Baumbreite (oder Pfadbreite) der endlichen Menge ausgeschlossener Minderjähriger bekannt ist, die (endliche) minimale Menge ausgeschlossener Minderjähriger bekannt wird berechenbar.

Es ist nicht einmal bekannt, ob die (endliche) minimale Menge ausgeschlossener Minderjähriger für die Vereinigung (die trivial geringfügig geschlossen ist) von zwei Klassen kleiner geschlossener Graphen, die jeweils durch ihre jeweilige endliche Menge ausgeschlossener Minderjähriger gegeben sind, berechnet werden kann, wenn keine Informationen vorliegen über Baumbreite (oder Pfadbreite) ist verfügbar. Oder vielleicht wurde in der Zwischenzeit sogar bewiesen, dass es im Allgemeinen nicht berechenbar ist.

Thomas Klimpel
quelle

G

$\mathcal G$

m (G)

$m(\mathcal G)$

f (n) = max {m (G_{1} \cup G_{2}) ∣ m (G_{1}), m (G_{2}) \leq n}

$f(n)=\max \{m(\mathcal G_1 \cup \mathcal G_2)\mid m(\mathcal G_1),m(\mathcal G_2)\le n\}$

f (n)

$f(n)$

f (n)

$f(n)$

@domotorp Ich stimme zu, guter Punkt. Ich habe einige Ideen für solche Beispiele, aber ich habe den Eindruck, dass die Wachstumsrate aller meiner Beispiele (die im Grunde versuchen, mit der "Gitter" -Dimension zu spielen) innerhalb von ELEMENTARY bleiben wird. Ich glaube jedoch, wenn ich Zeit in diese Fragen investieren wollte, sollte ich zuerst eine Literaturstudie darüber machen, was in den Jahren 2000-2018 passiert ist, vielleicht indem ich mir Papiere anschaue, die die mir bekannten Papiere zitieren, oder indem ich nachschaue bei späteren Veröffentlichungen der Autoren, die an diesen Fragen gearbeitet haben.

Thomas Klimpel

Ich

verstehe

@domotorp Es wurde gezeigt, dass die minimale Anzahl ausgeschlossener Minderjähriger für die Gewerkschaft im Jahr 2008 berechenbar ist: logo.las.tu-berlin.de/Members/Kreutzer/Publications/…

Thomas Klimpel

Gibt es einen Algorithmus, der die verbotenen Minderjährigen findet?

Antworten: