Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 14 down vote accepted

In one of my blog posts, 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 is in $NP \cap coNP$. This is a natural graph problem that is not known to be in $P$.

share|cite|improve this answer
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 Apr 19 '12 at 11:26
Unfortunately, I am not aware of such survey. – Shiva Kintali Apr 20 '12 at 23:14

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

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

share|cite|improve this answer
Thanks Daniel for your answer. – Mohammad Al-Turkistany Apr 19 '12 at 11:23

Kuperberg recently proved that knottedness (of a given knot diagram) is in NP ∩ coNP, 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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