# GI-hard graph problem not known to be $NP$-complete

Graph Isomorphism ($GI$) is good candidate for $NP$-intermediate problem. $NP$-intermediate problems exist unless $P=NP$. I'm looking for natural problem that is hard for $GI$ under Karp reduction (A graph problem $X$ such that $GI <_p^m X$).

Is there a natural $GI$-hard graph problem that is neither $GI$-equivalent nor known to be $NP$-complete?

• GI-equivalent under Karp reduction. – Mohammad Al-Turkistany Dec 6 '13 at 9:18
• candidates: problems between P and NPC – vzn Dec 6 '13 at 17:28
• It seems possible to construct an infinite hierarchy of such problems, by blending in "just enough of" Clique into GI, in a variant of Ladner's delayed diagonalization. See also the similar construction suggested by Bodirsky/Chen/Grohe/Thurley/Weyer. – András Salamon Dec 6 '13 at 22:35
• By the way, you might change the title to "GI-hard graph problem not known to be NP-complete." My first thought when I saw the current title was "Ring Isomorphism!" but the answer you found is (I think) significantly more interesting. – Joshua Grochow Feb 9 '14 at 15:15
• @JoshuaGrochow Thanks for your feedback. What do you suggest? Notice that I'm interested in graph problems. – Mohammad Al-Turkistany Feb 9 '14 at 15:17

After extensive search, I found the Legitimate Vertex Deck problem (LVD) which is related to the famous Graph Reconstruction conjecture. A deck of graph $G(V, E)$ is a multi-set of graphs $F = \{G_1,G_2, . . . , G_n\}$ such that $G_i$ is isomorphic to $G−v_i$ ($G-v$ is a graph obtained from $G$ by removing $v$ and its incident edges). ($|V|=n$)
The k-LEGITIMATE VERTEX-SUBDECK problem, given multi-set of graphs $F= \{G_1,G_2, . . . , G_k\}$, Decide whether there is a graph $G$ such that $F$ is a subset of its vertex-deck (k-LVD =$\{[G_1, . . . , G_k]|(∃G)[[G_1, . . . , G_k] ⊆ vertex-deck(G)]\}$) where $k \ge 3$
k-LVD problem is $GI$-hard and is not known to be $GI$-equivalent. It is open problem whether k-LVD is $NP$-complete (for $k \ge 3$). See the open problems section of Complexity results in graph reconstruction.
Also, the paper suggests the existence of a problem of intermediate complexity between $GI$ and k-LVD. The problem is LVD= n-LVD where all $n$ candidate cards are given (Input for LVD is $F= \{G_1,G_2, . . . , G_n \})$.
A simpler problem could be WEIGHTED_HYPERGRAPH_ISOMORPHISM. You are given two hypergraphs $G_1$ and $G_2$ on $n$ vertices with weighted hyper-edges, decide if there is a vertex permutation $pi$ turning $G_1$ into $G_2$.