Estoy considerando clases de gráficos que pueden caracterizarse por subgrafos prohibidos.
Si una clase de gráfico tiene un conjunto finito de subgrafos prohibidos, entonces hay un algoritmo de reconocimiento de tiempo polinómico trivial (uno puede usar la fuerza bruta). Pero una familia infinita de subgrafos prohibidos no implica dureza: hay algunas clases con una lista infinita de subgrafos prohibidos de tal manera que el reconocimiento también se puede probar en tiempo polinómico. Los gráficos Chordal y Perfect son ejemplos pero, en esos casos, hay una estructura "agradable" en la familia prohibida.
¿Existe alguna relación conocida entre la dureza del reconocimiento de una clase y el "mal comportamiento" de la familia prohibida? Tal relación debería existir? Este "mal comportamiento" se ha formalizado en alguna parte?
fuente
La respuesta de @Hugo es realmente agradable, y aquí quiero agregar algunas opiniones personales.
Hay familias relacionadas similares a las gráficas en la familia F y F '. Los gráficos de la familia B1 en el artículo generalmente se llaman pirámides. Y los gráficos en la familia B2 generalmente se llaman prismas. Vea la respuesta aquí para una ilustración. En la literatura sobre problemas de detección de subgrafos inducidos, se usaron para detectar agujeros pares / impares, que son ciclos sin acordes con longitud par / impar. Según el famoso teorema del gráfico perfecto fuerte, un gráfico G es perfecto si G y el complemento de G no contienen agujeros impares.
Para las familias de pirámides y prismas, de hecho, hay diferencias entre ellas: una tiene un subárbol inducido de tres hojas y la otra no. Esto se llama el problema "tres en un árbol" , que ha sido estudiado por Chudnovsky y Seymour. Es sorprendente que determinar si hay un árbol inducido que contiene tres nodos dados es manejable, mientras que el problema de "cuatro en un árbol centrado" es NP-difícil . (Un árbol centrado es un árbol con como máximo un nodo con un grado mayor que 2.) Las diferencias entre F y F 'parecen ser causadas por la misma razón.
Pero parece que una caracterización completa sigue siendo difícil, porque ni siquiera conocemos la complejidad de detectar gráficos en algunas de las familias que se ve lo suficientemente simple, como gráficos sin agujeros impares (!). Y para las familias que sabemos que existe un algoritmo de tiempo polinómico, como gráficos perfectos y gráficos libres de agujeros, aunque existen estrategias generales (basadas en descomposiciones) para diseñar un algoritmo, uno debe proporcionar un teorema estructural específico para ellos. Este suele ser un proceso que depende de la familia, y la mayoría de las veces las pruebas son realmente largas. ( Aquí hay un ejemplo para el gráfico sin agujeros pares, donde el papel tiene más de 90 páginas).
Aun así, sería interesante tener algunas clasificaciones para los problemas de detección de subgrafos inducidos, en el sentido del problema de tres en un árbol.
fuente