¿Hay algún algoritmo que encuentre a los menores prohibidos?

El teorema de Robertson-Seymour dice que cualquier familia $\mathcal G$ de gráficas menores cerradas puede caracterizarse por un número finito de menores prohibidos.

¿Existe algún algoritmo que para una entrada $\mathcal G$ dé salida a los menores prohibidos o es indecidible?

Obviamente, la respuesta puede depender de cómo se describe $\mathcal G$ en la entrada. Por ejemplo, si $\mathcal G$ es dada por un $M_\mathcal G$ que puede decidir la membresía, ni siquiera podemos decidir si $M_\mathcal G$ alguna vez rechaza algo. Si $\mathcal G$ es dada por muchos menores prohibidos, bueno, eso es lo que estamos buscando. Me gustaría saber la respuesta si se garantiza que $M_\mathcal G$ se detendrá en cualquier $G$ en un período de tiempo fijo en $|G|$ . También me interesan los resultados relacionados, donde se demuestra que $\mathcal G$ tiene un cierre menor con algún otro certificado (como en el caso de $TFNP$ oPRUEBA INCORRECTA).

Actualización: La primera versión de mi pregunta resultó ser bastante fácil, basada en las ideas de Marzio y Kimpel, considere la siguiente construcción. $M_\mathcal G$ acepta un gráfico en $n$ vértices si y solo si $M$ no se detiene en $n$ pasos. Este es un cierre menor y el tiempo de ejecución depende solo de $|G|$ .

graph-theory decidability graph-minor domotorp
fuente

está representado por un TM

siempre detenido , puede reducir el problema de detención: dado

build

que genera sí si y solo si

detiene exactamente en

pasos (

es una enumeración gráfico estándar).

acepta como máximo una menor prohibido, por lo

es una familia de menor importancia-cerrado, por lo que el problema es indecidible.

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, entendí mal la pregunta. Tal vez una solución es:

busca el primer

tal que

detiene exactamente en

pasos y luego acepta si

no es menor de

; rechazar lo contrario.

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 Sí, para simplificar:

acepta un gráfico en

vértices si y solo si

no se detiene en

pasos. Este es un cierre menor y el tiempo de ejecución depende solo de

M_{G}

$M_\mathcal G$

n

$n$

M

$M$

n

$n$

| G |

$|G|$

domotorp

Bueno, interpreto detener que si

detiene en

pasos, entonces también decimos que se detiene en

pasos.

M

$M$

2

$2$

3

$3$

domotorp

@domotorp Dado que su construcción funciona (si no me equivoco) y responde una de sus preguntas (y como Marzio De Biasi y yo tratamos de llegar a una construcción tan simple sin éxito), creo que debería convertir su construcción en un respuesta adecuada Puede convertirlo en una wiki comunitaria si se siente incómodo al responder su propia pregunta. Alternativamente, puede editar su pregunta y agregar la respuesta allí.

Thomas Klimpel el

Respuestas:

La respuesta de Mamadou Moustapha Kanté (quien realizó su doctorado bajo la supervisión de Bruno Courcelle) a una pregunta similar cita una Nota sobre la computabilidad de los conjuntos de obstrucción de gráficos menores para ideales monádicos de segundo orden (1997) por B. Courcelle, R. Downey y M. Becarios para un resultado de no computabilidad (para clases de grafos definibles por MSOL , es decir, clases definidas por una fórmula Monadic de segundo orden) y Las obstrucciones de un conjunto de grafos cerrados menores definidos por una gramática libre de contexto (1998) por B Courcelle y G. Sénizer solicitan un resultado de computabilidad (para las clases de gráficos definibles por FC , es decir, las clases definidas por una gramática de Reemplazo de Hyperedge).

La diferencia crucial entre el caso computable y el no computable es que las clases de gráficos definibles por HR (menor cerrado) tienen un ancho de árbol limitado, mientras que las clases de gráficos definibles por MSOL (menor cerrado) no necesitan tener un ancho de árbol limitado. De hecho, si una clase de gráfico definible por MSOL (menor cerrado) tiene un ancho de árbol acotado, entonces también es definible por HR.

El ancho del árbol parece ser realmente la parte crucial para separar los casos computables de los no computables. Otro resultado conocido (por M. Fellows y M􏰊.􏰊 Langston) básicamente dice que si se conoce un límite para el ancho máximo de árbol (o ancho de ruta) del conjunto finito de menores excluidos, entonces el conjunto mínimo (finito) de menores excluidos se convierte en calculable.

Ni siquiera se sabe si el conjunto mínimo (finito) de menores excluidos para el sindicato (que es trivialmente menor cerrado) de dos clases de gráficos menores cerrados cada uno dado por su respectivo conjunto finito de menores excluidos se puede calcular, si no hay información sobre el ancho de árbol (o ancho de ruta) está disponible. O tal vez incluso se ha demostrado mientras tanto que no es computable en general.

Thomas Klimpel
fuente

Esta última parte es bastante interesante. Si comprende bien, esto implica lo siguiente. Para una familia de grafos

G

$\mathcal G$ , denotamos por

m (G)

$m(\mathcal G)$ el tamaño del menor prohibido mínimo más grande. Dejar

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\}$ . Then there is no known recursive upper bound for

f (n)

$f(n)$ . Do you know some examples that show that

f (n)

$f(n)$ grows very fast?

domotorp

@domotorp I agree, good point. I do have some ideas for such examples, but I have the impression that the growth rate of all my examples (which basically try to play with "grid" dimension) will stay within ELEMENTARY. However, I believe that if I wanted to invest time into those questions, then I should first do a literature study about what happened in the years 2000-2018, perhaps by looking at papers that quote the papers that I know about, or by looking at later publications of the authors which worked on those questions.

Thomas Klimpel

I see - well, I'm not desperate to know the answer, just I got surprised and became curious...

domotorp

@domotorp The minimal set of excluded minors for the union has been shown to be computable in 2008: logic.las.tu-berlin.de/Members/Kreutzer/Publications/…

Thomas Klimpel