Problema de gráfico duro GI que no se sabe que es completo

15

El isomorfismo gráfico ( ) es un buen candidato para el intermedio . : existen problemas intermedios a menos que . Estoy buscando un problema natural que sea difícil para bajo la reducción de Karp (un problema de gráfico tal que ).GINPNPP=NPGIXGI<pmX

¿Existe un problema natural de gráfico duro que no es equivalente a ni se sabe que es completo?GIGINP

Mohammad Al-Turkistany
fuente
IG equivalente bajo reducción de Karp.
Mohammad Al-Turkistany
1
candidatos: problemas entre P y NPC
vzn
2
Parece posible construir una jerarquía infinita de tales problemas, combinando "solo lo suficiente" de Clique en GI, en una variante de la diagonalización retrasada de Ladner. Vea también la construcción similar sugerida por Bodirsky / Chen / Grohe / Thurley / Weyer.
András Salamon
Por cierto, puede cambiar el título a "Problema de gráfico duro GI que no se conoce como NP completo". Mi primer pensamiento cuando vi el título actual fue "¡Isomorfismo de anillo!" pero la respuesta que encontraste es (creo) significativamente más interesante.
Joshua Grochow
@ JoshuaGrochow Gracias por sus comentarios. ¿Que sugieres? Tenga en cuenta que estoy interesado en los problemas de gráficos.
Mohammad Al-Turkistany

Respuestas:

8

Después de una búsqueda exhaustiva, encontré el problema de la cubierta de vértice legítimo (LVD) que está relacionado con la famosa conjetura de reconstrucción de gráficos . Una baraja de gráfico es un multi-conjunto de gráficos F = { G 1 , G 2 , . . . , G n } tal que G i es isomorfo a G - v i ( G - v es un gráfico obtenido de G al eliminar vG(V,E)F={G1,G2,...,Gn}GiGviGvGvy sus bordes incidentes). ( )|V|=n

El problema VERTEX-subdeck k-legítimos, dado multi-conjunto de gráficos , decidir si existe un gráfico G tal que F es un subconjunto de su vértice-cubierta ( k-LVD = { [ G 1 , . . . , G k ] | ( G ) [ [ G 1 , . . . , GF={G1,G2,...,Gk}GF ) donde k 3{[G1,...,Gk]|(G)[[G1,...,Gk]vertexdeck(G)]}k3

El problema de k-LVD es duro y no se sabe que sea G I -equivalente. Es un problema abierto si k-LVD es N P- completo (para k 3 ). Consulte la sección de problemas abiertos de Resultados de complejidad en la reconstrucción de gráficos .GIGyoNPk3

Además, el documento sugiere la existencia de un problema de complejidad intermedia entre y k-LVD . El problema es LVD = n-LVD donde todos los n se dan tarjetas de candidatos (Entrada para LVD es F = { G 1 , G 2 , . . . , G n } ) .GInF={G1,G2,...,Gn})

Mohammad Al-Turkistany
fuente
0

Un problema más simple podría ser WEIGHTED_HYPERGRAPH_ISOMORPHISM. Se le dan dos hipergrafías y G 2 en n vértices con hiper-bordes ponderados, decida si hay una permutación de vértice p i convirtiendo G 1 en G 2 .G1G2npiG1G2


fuente