Graphprobleme mit guter Charakterisierung, aber nicht bekannt in

Ein Entscheidungsproblem ist gut charakterisiert, wenn es sich in . Viele natürliche Graphprobleme haben gute Charakterisierungen. Zum Beispiel liefert Kuratuwskis Theorem eine gute Charakterisierung planarer Graphen. Der Satz von Konig liefert eine gute Charakterisierung von zweigeteilten Graphen. Der Satz von Tutte bietet eine gute Charakterisierung von Graphen, die perfekt übereinstimmen. Der Euler-Satz liefert eine gute Charakterisierung der Eulerschen Graphen. Alle diese Erkennungsprobleme haben Polynomzeitalgorithmen.$NP \cap coNP$

Gibt es ein natürliches Graphproblem, das eine gute Charakterisierung aufweist, von dem jedoch nicht bekannt ist, dass es in ? Ein Hinweis auf eine Übersicht über solche Probleme wäre wünschenswert.$P$

$NP \cap coNP$$P$

Paritätsspiele und stochastische Spiele können als "Grafikprobleme" betrachtet werden.

Auch das Two Bicliques Problem ist in$NP \cap coNP$$P$

$NP\cap coNP$$P$

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

Beachten Sie jedoch, dass ein Paritätsspiel durch ein mit Anmerkungen versehenes gerichtetes Diagramm definiert wird, sodass Sie es möglicherweise nicht als "natürliches Diagrammproblem" betrachten möchten.

Kuperberg hat kürzlich bewiesen, dass die Knotigkeit (eines gegebenen Knotendiagramms) in NP ∩ coNP liegt , unter der Annahme, dass die verallgemeinerte Riemann-Hypothese wahr ist. Ein Knotendiagramm ist nah genug an einem Diagramm, sodass ich denke, dass dies als Antwort auf Ihre Frage gilt.