GI-hartes Graph-Problem, von dem nicht bekannt ist, dass es

15

Der Graphisomorphismus ( ) ist ein guter Kandidat für Zwischenprobleme. Zwischenprobleme bestehen nur, wenn . Ich suche nach einem natürlichen Problem, das für den unter Karp-Reduktion schwer ist (Ein Graph-Problem , bei dem ).GINPNPP=NPGIXGI<pmX

Gibt es ein natürliches -Hartgraph-Problem, das weder G I -äquivalent ist noch als N P -vollständig bekannt ist?GIGINP

Mohammad Al-Turkistany
quelle
GI-Äquivalent unter Karp-Reduktion.
Mohammad Al-Turkistany
1
Kandidaten: Probleme zwischen P und NPC
vzn
2
Es scheint möglich zu sein, eine unendliche Hierarchie solcher Probleme zu konstruieren, indem man "gerade genug" Clique in GI einblendet, in einer Variante von Ladners verzögerter Diagonalisierung. Siehe auch die von Bodirsky / Chen / Grohe / Thurley / Weyer vorgeschlagene ähnliche Konstruktion.
András Salamon
Übrigens könnten Sie den Titel in "GI-hartes Graph-Problem, von dem nicht bekannt ist, dass es NP-vollständig ist" ändern. Mein erster Gedanke, als ich den aktuellen Titel sah, war "Ring Isomorphism!" Aber die Antwort, die Sie gefunden haben, ist (glaube ich) bedeutend interessanter.
Joshua Grochow
@ JoshuaGrochow Vielen Dank für Ihr Feedback. Was schlagen Sie vor? Beachten Sie, dass ich an Grafikproblemen interessiert bin.
Mohammad Al-Turkistany

Antworten:

8

Nach umfangreicher Suche fand ich das legitime Vertex-Deck-Problem (LVD), das mit der berühmten Graph-Rekonstruktions-Vermutung zusammenhängt . Ein Deck des Graphen ist ein Multi-Satz von Graphen , F = { G 1 , G 2 , . . . , G n }, so dass G i isomorph zu G - v i ist ( G - v ist ein Graph, der aus G durch Entfernen von v erhalten wirdG(V,E)F={G1,G2,...,Gn}GiGviGvGvund seine Einfallskanten). ( )|V|=n

Das K-BERECHTIGTES VERTEX-Subdeck Problem, da Mehr Satz von Graphen , , Entscheiden , ob es einen Graph G , so dass F eine Teilmenge seines Scheitels-Deck (ist k-LVD = { [ G 1 , . . . , G k ] | ( G ) [ [ G 1 , . . . , GF={G1,G2,...,Gk}GF )wobei k 3{[G1,...,Gk]|(G)[[G1,...,Gk]vertexdeck(G)]}k3

Das k-LVD- Problem ist -hart und es ist nicht bekannt, dass es G I -äquivalent ist. Es ist offen , ob Problem k-LVD ist N P -komplette (für k 3 ). Informationen zur Rekonstruktion von Diagrammen finden Sie im Abschnitt "Offene Probleme" unter " Komplexitätsergebnisse" .GIGINPk3

Die Arbeit legt auch die Existenz eines Problems mittlerer Komplexität zwischen und k-LVD nahe . Das Problem ist , LVD = n-LVD , in der alle n Kandidaten - Karten gegeben sind (Eingang für LVD ist F = { G 1 , G 2 , . . . , G n } ) .GInF={G1,G2,...,Gn})

Mohammad Al-Turkistany
quelle
0

Ein einfacheres Problem könnte WEIGHTED_HYPERGRAPH_ISOMORPHISM sein. Sie erhalten zwei Hypergraphen und G 2 auf n Eckpunkten mit gewichteten Hyperkanten. Entscheiden Sie, ob es eine Eckpunktpermutation p i gibt , die G 1 in G 2 umwandelt .G1G2npiG1G2


quelle