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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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$.

Improve this answer
$\endgroup$
3
  • $\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, 2012 at 11:26
  • $\begingroup$ Unfortunately, I am not aware of such survey. $\endgroup$
    – Shiva Kintali
    Apr 20, 2012 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, 2017 at 1:38
7
$\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."

Improve this answer
$\endgroup$
1
  • $\begingroup$ "Document not found" in your posted link $\endgroup$
    – Mengfan Ma
    Jan 3, 2021 at 6:48
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.

Improve this answer
$\endgroup$

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.