<p>Determining the winner of a "parity game" is known to be in $NP\cap coNP$, but it is an outstanding open problem whether it is in $P$. See e.g.,</p>

<p><a href="http://lovelace.thi.informatik.uni-frankfurt.de/~klauck/XOR.pdf">http://lovelace.thi.informatik.uni-frankfurt.de/~klauck/XOR.pdf</a></p>

<p>Note, however, that a parity game is defined by an annotated directed graph, so you might not want to consider it a "natural graph problem."</p>

CC BY-SA 4.0
2021-01-03T06:48:37.830Z
"Document not found" in your posted link
Mengfan Ma
CC BY-SA 3.0
2012-04-18T18:43:23.237Z
2012-04-18T18:43:23.237Z
Daniel Marx
<p>Kuperberg recently proved that <a href="http://arxiv.org/abs/1112.0845">knottedness (of a given knot diagram) is in NP ∩ coNP</a>, assuming that the generalized Riemann hypothesis is true.  A knot diagram is close enough to a graph that I think this counts as an answer to your question.</p>

CC BY-SA 3.0
2012-04-19T19:01:47.327Z
2012-04-19T19:01:47.327Z
Timothy Chow
<p>In one of my <a href="http://kintali.wordpress.com/2010/06/06/np-intersect-conp/">blog posts</a>, I mentioned four problems (Factoring, Parity Games, Stochastic Games, A Lattice Problem) that are known to be in $NP \cap coNP$ but not known to be in $P$.</p>

<p>Parity Games and Stochastic Games can be considered as "graph problems".</p>

<p>Also, <a href="http://arxiv.org/abs/1104.3463">The Two Bicliques Problem</a> is in $NP \cap coNP$. This is a natural graph problem that is not known to be in $P$.</p>

CC BY-SA 3.0
2012-04-19T11:26:42.143Z
Thanks Shiva for your nice answer. I guess Two Bicliques is natural graph problem. Are aware of a survey of such graph problems especially the longest standing open problems?
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-04-20T23:14:15.673Z
Unfortunately, I am not aware of such survey.
Shiva Kintali
CC BY-SA 3.0
2017-03-13T01:38:01.050Z
Parity games can now at least be solved in quasipolynomial time, see [this answer](http://cs.stackexchange.com/questions/16399/is-it-possible-to-solve-parity-game-problem-in-polynomial-time/71442#71442). Maybe it is not so important after all, that they cannot be solved in polynomial time. They can be solved in practice, and that is what counts most.
Thomas Klimpel
CC BY-SA 3.0
2012-04-18T19:46:11.880Z
2012-04-18T19:52:13.120Z
2012-04-18T19:52:13.120Z
Shiva Kintali
<p>A decision problem has good characterization if it is in $NP \cap coNP$. Many natural graph problems have good characterizations. For instance, Kuratuwski's Theorem gives good characterization of planar graphs. Konig's Theorem gives good characterization of bipartite graphs. Tutte's Theorem gives good characterization of graphs that have perfect matching. Euler's Theorem gives good characterization of Eulerian graphs. All these recognition problems have polynomial-time algorithms.</p>

<p>Is there a natural graph problem that has good characterization but not known to be in $P$? A pointer to a survey of such problems would be appreciated.</p>

<cc.complexity-theory><graph-theory><proof-complexity>
Graph problems with good characterization but not known to be in $P$
Mohammad Al-Turkistany
# Graph problems with good characterization but not known to be in $P$

(Asked by: username_0 on 2012-04-18)

A decision problem has good characterization if it is in $NP \cap coNP$. Many natural graph problems have good characterizations. For instance, Kuratuwski's Theorem gives good characterization of planar graphs. Konig's Theorem gives good characterization of bipartite graphs. Tutte's Theorem gives good characterization of graphs that have perfect matching. Euler's Theorem gives good characterization of Eulerian graphs. All these recognition problems have polynomial-time algorithms.

Is there a natural graph problem that has good characterization but not known to be in $P$? A pointer to a survey of such problems would be appreciated.

**Tags:** cc.complexity-theory, graph-theory, proof-complexity

---

## 3 answers

### Answer by username_4 on 2012-04-18. Score: 14 | Accepted answer

In one of my [blog posts](http://kintali.wordpress.com/2010/06/06/np-intersect-conp/), I mentioned four problems (Factoring, Parity Games, Stochastic Games, A Lattice Problem) that are known to be in $NP \cap coNP$ but not known to be in $P$.

Parity Games and Stochastic Games can be considered as "graph problems".

Also, [The Two Bicliques Problem](http://arxiv.org/abs/1104.3463) is in $NP \cap coNP$. This is a natural graph problem that is not known to be in $P$.

> **Comments:**
> **username_0**: Thanks Shiva for your nice answer. I guess Two Bicliques is natural graph problem. Are aware of a survey of such graph problems especially the longest standing open problems?  
> **username_4**: Unfortunately, I am not aware of such survey.  
> **username_5**: Parity games can now at least be solved in quasipolynomial time, see [this answer](http://cs.stackexchange.com/questions/16399/is-it-possible-to-solve-parity-game-problem-in-polynomial-time/71442#71442). Maybe it is not so important after all, that they cannot be solved in polynomial time. They can be solved in practice, and that is what counts most.  

---

### Answer by username_1 on 2012-04-18. Score: 7

Determining the winner of a "parity game" is known to be in $NP\cap coNP$, but it is an outstanding open problem whether it is in $P$. See e.g.,

<http://lovelace.thi.informatik.uni-frankfurt.de/~klauck/XOR.pdf>

Note, however, that a parity game is defined by an annotated directed graph, so you might not want to consider it a "natural graph problem."

> **Comments:**
> **username_2**: "Document not found" in your posted link  

---

### Answer by username_3 on 2012-04-19. Score: 6

Kuperberg recently proved that [knottedness (of a given knot diagram) is in NP ∩ coNP](http://arxiv.org/abs/1112.0845), assuming that the generalized Riemann hypothesis is true. A knot diagram is close enough to a graph that I think this counts as an answer to your question.


---

