Problème de graphe dur non connu pour être complet

L'isomorphisme graphique ( ) est un bon candidat pour un problème intermédiaire . problèmes intermédiaires existent sauf si . Je recherche un problème naturel difficile pour sous réduction de Karp (Un problème graphique tel que ).$GI$$NP$$NP$$P=NP$$GI$$X$$GI <_p^m X$

Existe-t-il un problème naturel de graphe dur qui n'est ni équivalent ni connu pour être complet?$GI$$GI$$NP$

Après des recherches approfondies, j'ai trouvé le problème de Deck de sommet légitime (LVD) qui est lié à la fameuse conjecture de reconstruction graphique . Un jeu de graphes est un multi-ensemble de graphes tel que est isomorphe à ( est un graphe obtenu à partir de en supprimant et ses bords incidents). ( )$G(V, E)$$F = \{G_1,G_2, . . . , G_n\}$$G_i$$G−v_i$$G-v$$G$$v$$|V|=n$

Le problème k-LEGITIMATE VERTEX-SUBDECK, étant donné plusieurs ensembles de graphiques , Décider s'il existe un graphe tel que est un sous-ensemble de son vertex-deck ( k-LVD = ) où$F= \{G_1,G_2, . . . , G_k\}$$G$$F$$\{[G_1, . . . , G_k]|(∃G)[[G_1, . . . , G_k] ⊆ vertex-deck(G)]\}$$k \ge 3$

Le problème k-LVD est de type et n'est pas connu comme étant équivalent . Le problème est de savoir si k-LVD est complet (pour ). Voir la section des problèmes ouverts des résultats de complexité dans la reconstruction de graphes .$GI$$GI$$NP$$k \ge 3$

En outre, l'article suggère l'existence d'un problème de complexité intermédiaire entre et k-LVD . Le problème est LVD = n-LVD où toutes les cartes candidates sont données (l'entrée pour LVD est .$GI$$n$$F= \{G_1,G_2, . . . , G_n \})$

Un problème plus simple pourrait être WEIGHTED_HYPERGRAPH_ISOMORPHISM. On vous donne deux hypergraphes et sur sommets avec des hyper-arêtes pondérées, décidez s'il y a une permutation de sommet transformant en .G 2 n p i G 1 G $G_1$$G_2$$n$$pi$$G_1$$G_2$