<p>After extensive search, I found the Legitimate Vertex Deck problem (LVD) which is related to the famous <a href="http://en.wikipedia.org/wiki/Reconstruction_conjecture">Graph Reconstruction conjecture</a>. 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$)</p>

<p>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 (<strong>k-LVD</strong> =$ \{[G_1, . . . , G_k]|(∃G)[[G_1, . . . , G_k] ⊆ vertex-deck(G)]\}$) 
where $k \ge 3$</p>

<p><strong>k-LVD</strong> problem is $GI$-hard and is not known to be $GI$-equivalent. It is open problem whether <strong>k-LVD</strong> is $NP$-complete (for $k \ge 3$). See the open problems section of <a href="http://www.sciencedirect.com/science/article/pii/S0166218X06002228">Complexity results in graph reconstruction</a>. </p>

<p>Also, the paper suggests the existence of a problem of intermediate complexity between $GI$ and <strong>k-LVD</strong>. The problem is <strong>LVD</strong>= <strong>n-LVD</strong> where all $n$ candidate cards are given (Input for <strong>LVD</strong> is $F= \{G_1,G_2, . . . , G_n \})$. </p>

CC BY-SA 3.0
2013-12-14T20:25:00.623Z
2013-12-17T08:12:20.053Z
2013-12-17T08:12:20.053Z
Mohammad Al-Turkistany
<p>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 &lt;_p^m X$).</p>

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

CC BY-SA 3.0
2013-12-06T09:18:41.043Z
GI-equivalent under Karp reduction.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-12-06T17:28:44.917Z
candidates: [problems between P and NPC](http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/)
vzn
CC BY-SA 3.0
2013-12-06T22:35:56.813Z
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
CC BY-SA 3.0
2014-02-09T15:15:55.400Z
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
CC BY-SA 3.0
2014-02-09T15:17:51.463Z
@JoshuaGrochow Thanks for your feedback. What do you suggest? Notice that I'm interested in graph problems.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-09T15:30:49.240Z
@MohammadAl-Turkistany: I already made the suggestion in my previous comment (though I admit it was easy to miss). Just add the word graph to the title: "GI-hard *graph* problems not known..."
Joshua Grochow
CC BY-SA 3.0
2014-02-09T15:43:32.463Z
Thanks a lot @JoshuaGrochow. I edited the title as you suggested.
Mohammad Al-Turkistany
<cc.complexity-theory><graph-theory><graph-isomorphism><np-intermediate>
GI-hard graph problem not known to be $NP$-complete
Mohammad Al-Turkistany
# GI-hard graph problem not known to be $NP$-complete

(Asked by: username_0 on 2013-12-06)

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?

**Tags:** cc.complexity-theory, graph-theory, graph-isomorphism, np-intermediate
> **Comments:**
> **username_0**: GI-equivalent under Karp reduction.  
> **username_1**: candidates: [problems between P and NPC](http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/)  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_0**: @JoshuaGrochow Thanks for your feedback. What do you suggest? Notice that I'm interested in graph problems.  
> **username_3**: @MohammadAl-Turkistany: I already made the suggestion in my previous comment (though I admit it was easy to miss). Just add the word graph to the title: "GI-hard *graph* problems not known..."  
> **username_0**: Thanks a lot @JoshuaGrochow. I edited the title as you suggested.  

---

## 1 answers

### Answer by username_0 on 2013-12-14. Score: 8 | Accepted answer

After extensive search, I found the Legitimate Vertex Deck problem (LVD) which is related to the famous [Graph Reconstruction conjecture](http://en.wikipedia.org/wiki/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](http://www.sciencedirect.com/science/article/pii/S0166218X06002228).

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


---

