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?

  • $\begingroup$ GI-equivalent under Karp reduction. $\endgroup$ – Mohammad Al-Turkistany Dec 6 '13 at 9:18
  • 1
    $\begingroup$ candidates: problems between P and NPC $\endgroup$ – vzn Dec 6 '13 at 17:28
  • 2
    $\begingroup$ 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. $\endgroup$ – András Salamon Dec 6 '13 at 22:35
  • $\begingroup$ 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. $\endgroup$ – Joshua Grochow Feb 9 '14 at 15:15
  • $\begingroup$ @JoshuaGrochow Thanks for your feedback. What do you suggest? Notice that I'm interested in graph problems. $\endgroup$ – 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 \})$.

| cite | improve this answer | |

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$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.