Problemas abiertos relacionados con isomorfismo gráfico

18

Actualmente estoy haciendo una encuesta bibliográfica sobre el problema del isomorfismo gráfico (GI).

Me gustaría saber algunas preguntas abiertas relacionadas con lo siguiente

  1. ¿Cuáles son los parámetros del gráfico para los que la trazabilidad de parámetros fijos de GI es un problema abierto?

  2. ¿Cuáles son los parámetros del gráfico? Al fijarlos, no se conoce la solubilidad en tiempo polinómico de IG.

  3. La complejidad de GI cuando se restringe a muchas clases de gráficos es equivalente a GI general (GI-Completitud). ¿Cuáles son las clases de gráficos para las que no se conoce la integridad de GI?

Gracias.

graph-isomorphism fixed-parameter-tractable Kumar
fuente
3
No conozco ninguna respuesta definitiva a sus preguntas. Si encuentra respuestas parciales (lo que podría requerir mirar docenas de trabajos de investigación publicados), entonces sería excelente si pudiera vincular el resumen que crea, o dar sus aspectos más destacados, como respuesta.
András Salamon
re 3, pregunta. para las muchas clases de gráficas comprobadas como GI completas, ¿es la pregunta "no son X gráficas GI completas?" ¿abierto? ¿Tiene eso algún sentido? pregunta cs.se relacionadaXX
vzn

Respuestas:

13

Para la primera pregunta: el isomorfismo gráfico se ha considerado al menos para los siguientes parámetros para los que la trazabilidad de parámetros fijos aún está abierta.

  • ancho de ruta / ancho de árbol (ver [2], se ha preguntado aquí ), tal vez resuelto: http://arxiv.org/abs/1404.0818
  • ancho de banda / ancho de banda [1]
  • tamaño del conjunto de eliminación de vértices treewidth-k (número de conjunto de vértices de retroalimentación en [7])
  • ancho de distancia de árbol / camino (ver [1]), ancho de distancia de árbol conectado (ver [3], sin embargo, puede acercarse bastante al último, ver sección 6.4. de mi tesis de diploma ) : resuelto por Y. Otachi y P Schweitzer: http://arxiv.org/abs/1403.7238
  • ancho de camarilla / profundidad de arbusto (o profundidad SC) (ver [ 4 ])
  • grado máximo [5]
  • género [6] / número de cruce [8]

Tenga en cuenta que hay una investigación activa en curso para algunos de ellos.

[1]: K. Yamazaki, HL Bodlaender, B. de Fluiter y DM Thilikos. Isomorfismo para gráficos de ancho de distancia acotada. Algorithmica 24.2 (1999)

[2]: HL Bodlaender. Algoritmos polinomiales para isomorfismo de grafos e índice cromático en árboles parciales. Revista de Algoritmos 11.4 (1990)

[3]: Y. Otachi. Isomorfismo para gráficos de ancho de ruta conectado enlazado. Algoritmos y Computación. Springer, 2012

[ 4 ]: http://www.fi.muni.cz/~hlineny/res-en.html#recent

[5]: L. Babai y EM Luks. Etiquetado canónico de gráficos. STOC '83.

[6]: IS Filotti y JN Mayer. Un algoritmo de tiempo polinómico para determinar el isomorfismo de gráficos de género fijo. STOC '80 / G. Miller. Prueba de isomorfismo para gráficos de género acotado. STOC '80

[7]: S. Kratsch y P. Schweitzer. Isomorfismo para gráficos del número de conjunto de vértices de retroalimentación acotada. SWAT 2010

[8]: http://math.mit.edu/news/summer/SPURprojects/2012Velednitsky.pdf

frafl
fuente
1
En términos de investigación activa activa en esta área, sugeriría algunas referencias adicionales. [A] Este papel aquí de IPEC 2012, muestra el gráfico isomorfismo se fija-parámetro tratable en el árbol- profundidad de un gráfico, que es un parámetro relacionado con árbol de ancho. [B] Este documento aquí muestra que el isomorfismo gráfico para gráficos cordales es FPT en el tamaño del componente simplicial más grande.
Adam Bouland
3
Ssol
@Adam Bouland ¿Existe algún algoritmo de tiempo FPT o polinómico para el isomorfismo gráfico para el ancho de banda acotado?
Kumar
1
@ Kumar Es solucionable por tiempo múltiple pero no se sabe que sea FPT. Ver Yamazaki et al. [1] en la respuesta de frafl.
Yota Otachi
5

Para la tercera pregunta: el documento de la encuesta de Brandstadt, Le y Spinrad, Graph Classes: A Survey, SIAM, 1999, contiene varias clases de gráficos para las que no se conoce la integridad de GI. Una de esas clases son los gráficos trapezoidales . Otra clase son los gráficos de arco circular que se mencionan como problema abierto en la introducción del artículo, Tractabilidades e Intractabilidades en los gráficos de intersección geométrica de Uehara.

EDITAR : no se sabe que el problema de isomorfismo gráfico para torneos sea completo GI.

Mohammad Al-Turkistany
fuente
4

Para la tercera pregunta, también puede visitar www.graphclasses.org : inicie el applet de java y seleccione Problemas -> Problemas de límites / abiertos -> Isomorfismo gráfico.

Obtendrá una enorme lista de clases de gráficos para las cuales el estado del problema GI es desconocido para ISGCI (podría estar en P o GI completo); probablemente para algunos de ellos la integridad GI ya se ha resuelto, o simplemente todavía no se han estudiado; pero es un buen punto de partida para buscar documentos sobre ellos.

Marzio De Biasi
fuente