Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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$.