NP-Härte auf Cayley-Graphen

Was ist über die Komplexität von NP-harten Problemen in Cayley-Graphen bekannt?

Angenommen, der Graph wird explizit als Multiplikationstabelle der Gruppe und als Liste der Generatoren angegeben. Die Eingabelänge entspricht also der Größe des Diagramms. Können wir NP-vollständige Probleme in solchen Graphen (maximale Clique / maximaler Schnitt) in Polynomzeit lösen?

Was ist mit einigen Sonderfällen von Gruppen? Zum Beispiel (auch bekannt als zirkulierende Graphen) oder Z log ( n ) 2 . Das heißt, die Eingabe für das Problem ist der Satz von Generatoren (und 1 n , um die Größe des Graphen darzustellen).$\mathbb{Z}_n$$\mathbb{Z}_2^{\log(n)}$$1^n$

Da die Eingabegröße (eine Beschreibung der Gruppe und ihrer Generatoren) so viel kleiner sein kann als das Diagramm selbst, können selbst Standardprobleme bei der Optimierung von Polynom-Zeit-Diagrammen für Cayley-Diagramme schwierig werden. Beispielsweise sind kürzeste Wege in zirkulierenden Graphen (ein Sonderfall von Cayley-Graphen) NP-vollständig; siehe "On Routing in Circulant Graphs", Cai et al., COCOON 1999, doi: 10.1007 / 3-540-48686-0_36

Dies gilt natürlich nicht für die genaue Aussage des von Ihnen angegebenen Problems (wobei die Gruppe als Multiplikationstabelle angegeben wird, selbst ein Objekt mit einer Größe, die mit dem Cayley-Diagramm vergleichbar ist), aber es weist auf einen gewissen Sorgfaltsbedarf hin.