8
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mohammad Al-Turkistany Apr 19 '12 at 11:26
  • $\begingroup$ Unfortunately, I am not aware of such survey. $\endgroup$ – Shiva Kintali Apr 20 '12 at 23:14
  • $\begingroup$ Parity games can now at least be solved in quasipolynomial time, see this answer. 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. $\endgroup$ – Thomas Klimpel Mar 13 '17 at 1:38
6
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

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.