Existe-t-il un algorithme qui trouve les mineurs interdits?

Le théorème de Robertson – Seymour dit que toute famille $\mathcal G$ de graphes mineurs peut être caractérisée par un nombre fini de mineurs interdits.

Existe-t-il un algorithme qui, pour une entrée $\mathcal G$ délivre les mineurs interdits ou est-ce indécidable?

Évidemment, la réponse pourrait dépendre de la façon dont $\mathcal G$ est décrit dans l'entrée. Par exemple, si $\mathcal G$ est donné par un $M_\mathcal G$ qui peut décider de l'appartenance, nous ne pouvons même pas décider si $M_\mathcal G$ rejette quelque chose. Si $\mathcal G$ est donné par un nombre fini de mineurs interdits - eh bien, c'est ce que nous recherchons. Je serais curieux de connaître la réponse si $M_\mathcal G$ est garanti de s'arrêter sur n'importe quel $G$ dans un laps de temps fixe dans $|G|$ . Je suis également intéressé par tout résultat connexe, où $\mathcal G$ se révèle être mineur-fermé avec un autre certificat (comme dans le cas de $TFNP$ ouFAUX PREUVE).

Mise à jour: La première version de ma question s'est avérée assez facile, sur la base des idées de Marzio et Kimpel, envisagez la construction suivante. $M_\mathcal G$ accepte un graphe sur $n$ sommets si et seulement si $M$ ne s'arrête pas en $n$ étapes. Ceci est mineur fermé et le temps de fonctionnement dépend uniquement de $|G|$ .

graph-theory decidability graph-minor domotorp
la source

est représenté par un TM

toujours en arrêt , vous pouvez réduire le problème d'arrêt: étant donné

construire

qui renvoie oui si et seulement si

s'arrête exactement en

étapes (

est une énumération graphique standard).

accepte au plus un mineur interdit, si

est une famille de mineur fermé, d' où le problème est indécidable.

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

@ThomasKlimpel: Ops, j'ai mal compris la question. Peut-être qu'un correctif est:

recherche le premier

telle sorte que

s'arrête exactement en

étapes puis accepte si

n'est pas un mineur de

; rejeter autrement.

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$

Marzio De Biasi

@Marzio Oui, pour simplifier:

accepte un graphe sur

sommets si et seulement si

ne s'arrête pas en

étapes. Ceci est mineur fermé et le temps de fonctionnement dépend uniquement de

M_{G}

$M_\mathcal G$

n

$n$

M

$M$

n

$n$

| G |

$|G|$

domotorp

Eh bien, j'interprète le fait d'arrêter que si

s'arrête en

étapes, alors nous disons aussi qu'il s'arrête en

étapes.

M

$M$

2

$2$

3

$3$

domotorp

@domotorp Puisque votre construction fonctionne (si je ne me trompe pas), et répond à une de vos questions (et puisque Marzio De Biasi et moi avons essayé de proposer une construction aussi simple sans succès), je pense que vous devriez transformer votre construction en un bonne réponse. Vous pouvez en faire un wiki communautaire, si vous ne souhaitez pas répondre à votre propre question. Vous pouvez également modifier votre question et y ajouter la réponse.

Thomas Klimpel

Réponses:

La réponse de Mamadou Moustapha Kanté (qui a fait son doctorat sous la supervision de Bruno Courcelle) à une question similaire cite A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals (1997) par B.Courtelle , R. Downey, et M. Fellows pour un résultat non calculable (pour les classes de graphes définissables par MSOL , c'est-à-dire les classes définies par une formule de second ordre monadique) et Les obstructions d'un ensemble de graphiques fermés par des mineurs définis par une grammaire sans contexte (1998) par B Courcelle et G. Sénizergues pour un résultat de calculabilité (pour les classes de graphes définissables par HR , c'est-à-dire les classes définies par une grammaire Hyperedge Replacement).

La différence cruciale entre le cas calculable et le cas non calculable est que les classes de graphes définissables par HR (mineures fermées) ont une largeur d'arbre bornée, tandis que les classes de graphes définissables MSOL (mineures fermées) n'ont pas besoin d'avoir une largeur d'arbre bornée. En fait, si une classe de graphes définissable MSOL (fermée de façon mineure) a une largeur d'arbre bornée, elle peut également être définie par HR.

La largeur d'arbre semble être vraiment la partie cruciale pour séparer les cas calculables des cas non calculables. Un autre résultat connu (par M. Fellows et M􏰊.􏰊 Langston) dit essentiellement que si une limite pour la largeur maximale (ou largeur de chemin) de l'ensemble fini de mineurs exclus est connue, alors l'ensemble minimal (fini) de mineurs exclus devient calculable.

On ne sait même pas si l'ensemble minimal (fini) de mineurs exclus pour l'union (qui est trivialement mineur-fermé) de deux classes de graphiques fermées par des mineurs chacun donné par leur ensemble fini respectif de mineurs exclus peut être calculé, si aucune information sur la largeur d'arbre (ou la largeur de chemin) est disponible. Ou peut-être qu'il a même été prouvé entre-temps qu'il est non calculable en général.

Thomas Klimpel
la source

Cette dernière partie est assez intéressante. Si vous comprenez bien, cela implique ce qui suit. Pour une famille de graphes

, notons

la taille du plus grand mineur minime interdit. Soit

. Il n'y a donc pas de limite supérieure récursive connue pour

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)$ . Connaissez-vous des exemples qui montrent que

croît très rapidement?

f (n)

$f(n)$

domotorp

@domotorp Je suis d'accord, bon point. J'ai quelques idées pour de tels exemples, mais j'ai l'impression que le taux de croissance de tous mes exemples (qui essaient essentiellement de jouer avec la dimension "grille") restera dans ELEMENTARY. Cependant, je crois que si je voulais investir du temps dans ces questions, je devrais d'abord faire une étude de la littérature sur ce qui s'est passé dans les années 2000-2018, peut-être en consultant des articles qui citent les articles que je connais, ou en regardant lors de publications ultérieures des auteurs qui ont travaillé sur ces questions.

Thomas Klimpel

Je vois - eh bien, je ne suis pas désespéré de connaître la réponse, juste je me suis surpris et suis devenu curieux ...

domotorp

@domotorp L'ensemble minimal de mineurs exclus pour le syndicat s'est avéré calculable en 2008: logic.las.tu-berlin.de/Members/Kreutzer/Publications/…

Thomas Klimpel