15
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ GI-equivalent under Karp reduction. $\endgroup$ Dec 6, 2013 at 9:18
  • 1
    $\begingroup$ candidates: problems between P and NPC $\endgroup$
    – vzn
    Dec 6, 2013 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$ Dec 6, 2013 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$ Feb 9, 2014 at 15:15
  • $\begingroup$ @JoshuaGrochow Thanks for your feedback. What do you suggest? Notice that I'm interested in graph problems. $\endgroup$ Feb 9, 2014 at 15:17

2 Answers 2

8
$\begingroup$

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 \})$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This is GI-complete. $\endgroup$ Aug 16, 2020 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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