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

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 ).$GI$$NP$$NP$$P=NP$$GI$$X$$GI <_p^m X$

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

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 $G(V, E)$$F = \{G_1,G_2, . . . , G_n\}$$G_i$$G−v_i$$G-v$$G$$v$y 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 , . . . , $F= \{G_1,G_2, . . . , G_k\}$$G$$F$ ) donde k ≥ $\{[G_1, . . . , G_k]|(∃G)[[G_1, . . . , G_k] ⊆ vertex-deck(G)]\}$$k \ge 3$

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 .$GI$$GI$$NP$$k \ge 3$

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 } ) .$GI$$n$$F= \{G_1,G_2, . . . , G_n \})$

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 .$G_1$$G_2$$n$$pi$$G_1$$G_2$