Reverse Graph Spectra Problem?

25

Normalerweise erstellt man einen Graphen und stellt dann Fragen zur Eigenwertzerlegung der Adjazenzmatrix (oder eines nahen Verwandten wie dem Laplace ) (auch Spektren eines Graphen genannt ).

Aber was ist mit dem umgekehrten Problem? Gegeben Eigenwerte kann man (effizient) ein Diagramm finden , das diese Spektren hat?n

Ich vermute, dass dies im Allgemeinen schwierig ist (und möglicherweise mit GI vergleichbar ist), aber was ist, wenn Sie einige der Bedingungen ein wenig entspannen? Was ist, wenn Sie Bedingungen stellen, dass es keine Vielzahl von Eigenwerten gibt? Wie wäre es damit, Diagramme zuzulassen, die "nahe" Spektren durch eine Distanzmetrik aufweisen?

Alle Referenzen oder Ideen wären willkommen.

EDIT :

Wie Suresh betont, wird dieses Problem ziemlich trivial, wenn Sie ungerichtete gewichtete Diagramme mit Selbstschleifen zulassen. Ich hatte gehofft, Antworten auf ungerichtete, ungewichtete, einfache Diagramme zu erhalten, aber ich würde auch mit einfachen, ungewichteten, gerichteten Diagrammen zufrieden sein.

user834
quelle
2
Ich denke, Sie müssen möglicherweise die Frage auf "ungewichtete ungerichtete Diagramme ohne Selbstschleifen" oder so etwas ändern? Kann ich mir vorstellen, eine Diagonalmatrix mit den erforderlichen Eigenwerten zu konstruieren und als nicht zusammenhängenden Graphen mit gewichteten Selfloops zu deklarieren?
Suresh Venkat
6
Noch einfachere Frage (ich weiß die Antwort nicht) ist, wie man einfache zusammenhängende Graphen konstruiert, deren oberste Eigenwerte angegeben sind
Yaroslav Bulatov
5
Eine alternative Möglichkeit, die Frage zu formulieren (die Version mit einfachen ungerichteten Graphen), besteht darin, bei n reellen Zahlen (in einem bestimmten Format) zu entscheiden, ob es eine n × n symmetrische 0/1-Matrix mit Nulldiagonalen gibt, so dass ihre n Eigenwerte die sind gegebene Zahlen.
Tsuyoshi Ito
1
@ Jaroslaw: Ich bin mir nicht sicher, aber dieses Problem klingt für mich schwieriger als der Fall, in dem alle n Eigenwerte angegeben sind.
Tsuyoshi Ito
8
Winzige Beobachtung: Wenn wir keine Beschränkungen für die Eigenwerte haben, ist das Problem wirklich schwierig (auch ohne den algorithmischen Teil), da dies impliziert, dass der 57-reguläre Moore-Graph (nicht) existiert , dessen Eigenwerte alle bekannt sind.
Hsien-Chih Chang 張顯 張顯

Antworten:

10

Cvetcovic et al. In Abschnitt 3.3 von "Neueste Ergebnisse in der Theorie der Graphenspektren" gehen Algorithmen zur Konstruktion von Graphen mit gegebenem Spektrum in einigen speziellen Fällen durch

Jaroslaw Bulatow
quelle
10

Selbst die Frage, ob ein Graph mit einem bestimmten Spektrum existiert, ist eine schwierige Frage. Dies zeigt sich in dem offenen Problem, zu bestimmen, ob ein Graph von Umfang 5, Durchmesser 2 und Ordnung 3250 existiert, dessen Spektrum (falls vorhanden) bekannt ist.

Jernej
quelle
3

Ein weiteres Hindernis bei der Definition Ihrer Frage ist, dass es sich um isospektrale (gleiche Eigenwerte), aber nicht-isomorphe Graphen handelt. Welchen Graphen möchten Sie also in einem solchen Fall mit einer Liste von Eigenwerten? Vielleicht möchten Sie nur, dass ein Algorithmus ein zufälliges Element der Menge solcher nicht-isomorphen Graphen zurückgibt?

Dabacon
quelle
Ich habe etwas in der Art von Stichproben aus dem Raum der isospektralen Graphen gedacht, aber dies scheint, als würden wir schnell in ein GI-äquivalentes Problem abtauchen (daher mein Kommentar oben). Der Einfachheit halber könnten wir uns auf alle unterschiedlichen Eigenwerte beschränken (wenn IIC einen eindeutigen Graphen sicherstellt), aber ich versuche wirklich nur zu sehen, was bekannt ist oder was da draußen ist.
User834
5
Ich glaube nicht, dass unterschiedliche Eigenwerte die Rekonstruierbarkeit gewährleisten. Hier sind einige Spektren von Isospektraldiagrammen
Yaroslav Bulatov
3
Ich mag die zufällige Elementformulierung. Es würde mich interessieren, ob es dem GI entspricht. Ein Grund für mein Interesse an der Zufallselementformulierung ist die Frage, die ich in meinem Artikel mit Arora und Steurer zu einzigartigen Spielen aufgeworfen habe, ob Grafiken mit einem bestimmten Spektrum Expander für kleine Mengen sein können. Intuitiv kann man hoffen, dass ein zufälliger Graph mit diesem Spektrum der bestmögliche Expander für alle eingestellten Größen ist, und daher kann ein Einblick in umgekehrte Spektren dort nützlich sein.
Boaz Barak
@Yaroslav: Danke für diesen Link und danke, dass du mich korrigiert hast!
User834
1
@ user834: Betreff: Ihr Kommentar zu einem GI-äquivalenten Problem. Es ist zu beachten, dass die Bestimmung des Isomorphismus von Graphen mit begrenzter Eigenwertmultiplizität (insbesondere von Graphen ohne Mehrfacheigenwerte) in Polynomzeit erfolgen kann.
Joshua Grochow