Harte Probleme bei Grafiken höherer Gattungen

Planare Graphen haben die Gattung Null. Auf einem Torus einbettbare Grafiken haben höchstens die Gattung 1. Meine Frage ist einfach:

• Gibt es irgendwelche Probleme, die auf planaren Graphen polynomiell lösbar sind, auf Graphen der Gattung 1 jedoch NP-hart?

• Gibt es allgemeiner irgendwelche Probleme, die auf Graphen der Gattung g polynomisch lösbar sind, auf Graphen der Gattung> g jedoch NP-hart sind?

Dies ist Werbung für meine eigene Arbeit, aber die Überschreitung von Zahl und 1-Planarität ist in ebenen Graphen trivial lösbar, für Graphen der Gattung 1 jedoch schwierig. Siehe http://arxiv.org/abs/1203.5944

Wenn Spielzeugprobleme in Ordnung sind:

Sei und sei H ein Graph der Gattung g + 1 . Für φ einer CNF-Formel, lassen G & phgr; einige Codierung sein φ als ebenes Diagramm zuzüglich einer disjunkten Kopie von H .$g\in\mathbb{N}$$H$$g+1$$\phi$$G_\phi$$\phi$$H$

Bei gegebenem , das ein Graph der Gattung g + 1 ist , ist es NP-schwer zu entscheiden, ob ϕ erfüllbar ist. Dieses Problem wird jedoch trivial, wenn es auf Graphen der Gattung ≤ g beschränkt ist .$G_\phi$$g+1$$\phi$$\leq g$

$G$$g$$T=poly(n) + 2^{2g} O(m^3)$$m$$G$

Cai, Lu und Xia haben kürzlich die folgende Zweiteilung bei #CSP-Zählproblemen bewiesen:

Wir beweisen Komplexitätsdichotomiesätze im Rahmen der Zählung von CSP-Problemen. Die lokalen Einschränkungsfunktionen verwenden Boolesche Eingaben und können beliebige symmetrische Funktionen mit reellen Werten sein. Wir beweisen, dass jedes Problem in dieser Klasse genau drei Kategorien zugeordnet werden kann:

(1) solche, die auf allgemeinen Graphen nachvollziehbar sind (dh die Polynomzeit berechenbar sind), oder
(2) solche, die auf allgemeinen Graphen nachvollziehbar sind, aber auf ebenen Graphen nachvollziehbar sind , oder
(3) solche, die sogar nachvollziehbar sind auf ebenen Graphen.

Die Klassifizierungskriterien sind explizit.

$g$$g$$X_g$$g$$g$$g$$X_g$$g$

$\mathcal C$$\mathcal C$