Stark regelmäßiger Graph und GI-Vollständigkeit

16

Es ist nicht bekannt, ob der Graphisomorphismus (GI) für stark reguläre Graphen (SRGs) in P ist . Gibt es irgendwelche Hinweise, dass es GI- vollständig sein könnte oder nicht ? Gibt es in solchen Fällen starke Konsequenzen? (Ähnlich wie der Glaube, dass GI möglicherweise nicht NP-vollständig ist).

cc.complexity-theory graph-theory graph-algorithms graph-isomorphism structural-complexity DurgaDatta
quelle
6
Ich persönlich glaube, dass das Problem aufgrund des Spielman-Algorithmus für SRGs, der einen kleineren Exponenten hat als der von Luks für allgemeine Graphen, strikt einfacher ist als GI. Es scheint so viel mehr Struktur zu geben! (was letztendlich nichts bedeuten könnte)
Timothy Sun
2
Obwohl ich mit @TimothySun einverstanden bin, kenne ich keine formalen Gründe, um zu glauben, dass SRGI strikt einfacher ist als GI. Wenn es beispielsweise eine -Reduktion von GI zu SRGI gibt, ergibt dies einen besseren Algorithmus für GI als derzeit bekannt, aber wenn die Reduktion die Anzahl der Scheitelpunkte sogar auf dann hätte es diese überraschende Konsequenz nicht. Ich bezweifle, dass es irgendwelche Komplexitätsfolgen gibt, wenn ein Problem (bekanntermaßen auf GI reduziert) GI-vollständig ist, da es mit den meisten anderen Komplexitätsklassen so wenig zu tun hat (im Gegensatz zu der Tatsache, dass GI als NPC die PH zusammenbricht). Ö(n)Ö(n3/2)
Joshua Grochow

Antworten:

11

Ich glaube, dass alle bekannten GI-Vollständigkeitsergebnisse funktional sind (Definition in der Veröffentlichung), und Babai hat kürzlich gezeigt (ITCS 2014, freie Autorenkopie ), dass es keine funktionalen Ergebnisse gibt Reduktion von GI auf stark regulären GI.

Joshua Grochow
quelle