Membalikkan Masalah Spektra Grafik?

25

Biasanya seseorang membuat grafik dan kemudian mengajukan pertanyaan tentang dekomposisi nilai eigen matriks adjacency (atau kerabat dekat seperti Laplacian ) (juga disebut spektra grafik ).

Tapi bagaimana dengan masalah sebaliknya? Mengingat nilai eigen, bisa satu (efisien) menemukan grafik yang memiliki spektrum ini?n

Saya menduga bahwa secara umum ini sulit dilakukan (dan mungkin setara dengan GI) tetapi bagaimana jika Anda mengendurkan beberapa kondisi sedikit? Bagaimana jika Anda membuat kondisi bahwa tidak ada multiplisitas nilai eigen? Bagaimana dengan memungkinkan grafik yang memiliki spektrum "tutup" dengan metrik jarak?

Referensi atau ide apa pun akan diterima.

EDIT :

Seperti yang Suresh tunjukkan, jika Anda mengizinkan grafik tertimbang yang tidak diarahkan dengan loop otomatis, masalah ini menjadi sangat sepele. Saya berharap untuk mendapatkan jawaban pada set grafik sederhana tanpa arahan, tidak tertimbang tetapi saya akan senang dengan grafik diarahkan sederhana tertimbang juga.

ds.algorithms graph-theory graph-algorithms spectral-graph-theory pengguna834
sumber
2
Saya pikir Anda mungkin perlu mengubah pertanyaan menjadi 'grafik tidak terarah tanpa bobot tanpa loop otomatis' atau sesuatu seperti itu? Saya bisa membayangkan membangun matriks diagonal dengan nilai eigen yang diperlukan dan mendeklarasikannya sebagai grafik yang terputus dengan selfloop tertimbang?
Suresh Venkat
6
Bahkan pertanyaan yang lebih sederhana (saya tidak tahu jawabannya) adalah bagaimana membuat grafik terhubung sederhana yang beberapa nilai eigen utamanya diberikan
Yaroslav Bulatov
5
Cara alternatif untuk menyatakan pertanyaan (versi dengan grafik tidak berarah sederhana) adalah: diberikan n bilangan real (dalam beberapa format), putuskan apakah ada matriks 0/1 simetris nx n dengan nol diagonal sehingga n nilainya eigen adalah angka yang diberikan.
Tsuyoshi Ito
1
@Yaroslav: Saya tidak yakin, tapi masalah itu terdengar lebih sulit bagi saya daripada kasus di mana semua nilai eigen diberikan.
Tsuyoshi Ito
8
Pengamatan kecil: Jika kita tidak memiliki batasan pada nilai-nilai eigen, masalahnya sangat sulit (bahkan tidak termasuk bagian algoritmik) karena ini akan menyiratkan keberadaan (non-) ke grafik Moore 57-reguler , yang semua nilai eigennya diketahui.
Hsien-Chih Chang 張顯 之

Jawaban:

10

Cvetcovic et all dalam Bagian 3.3 dari "Hasil terbaru dalam teori spektrum grafik" membahas algoritma untuk membangun grafik yang diberi spektrum dalam beberapa kasus khusus

Yaroslav Bulatov
sumber
10

Bahkan menanyakan apakah grafik dengan spektrum yang diberikan ada adalah pertanyaan yang sulit. Ini disaksikan oleh masalah terbuka untuk menentukan apakah ada grafik dengan diameter 5 diameter 2 dan memesan 3250 yang spektrumnya (jika ada) diketahui.

Jernej
sumber
3

Salah satu kendala lain dalam mendefinisikan pertanyaan Anda adalah bahwa isospectral (nilai eigen yang sama) tetapi grafik non-isomorfik. Jadi diberi daftar nilai eigen dalam kasus seperti itu, grafik mana yang Anda inginkan? Mungkin Anda hanya ingin algoritma mengembalikan satu elemen acak dari set grafik non-isomorfik tersebut?

dabacon
sumber
Saya sedang memikirkan sesuatu di sepanjang garis pengambilan sampel dari ruang grafik yang isospectral tapi ini sepertinya kita dengan cepat turun ke masalah setara GI (jadi komentar saya di atas). Untuk kesederhanaan, kita dapat membatasi semua nilai eigen yang berbeda (yang, jika IIC memastikan grafik yang unik) tapi saya benar-benar hanya mencoba untuk melihat apa yang diketahui atau di luar sana.
user834
5
Saya tidak berpikir nilai eigen yang berbeda memastikan rekonstruktivitas, berikut adalah beberapa spektrum grafik isospektral
Yaroslav Bulatov
3
Saya suka formulasi elemen acak. Saya akan tertarik untuk mengetahui apakah itu setara dengan GI. Salah satu alasan saya tertarik pada formulasi elemen acak, adalah pertanyaan, yang diajukan dalam makalah saya dengan Arora dan Steurer tentang permainan unik, apakah grafik dengan spektrum tertentu dapat menjadi ekspander untuk set kecil. Secara intuitif, orang mungkin berharap bahwa grafik acak dengan spektrum ini akan menjadi expander terbaik untuk semua ukuran yang diatur, dan dengan demikian wawasan tentang spektrum terbalik dapat berguna di sana.
Boaz Barak
@Yaroslav: Terima kasih atas tautan itu dan terima kasih telah mengoreksi saya!
user834
1
@ user834: Re: komentar Anda tentang masalah setara GI. Perhatikan bahwa menentukan isomorfisme grafik dengan multiplisitas nilai eigen terbatas (khususnya, grafik tanpa nilai eigen ganda) dapat dilakukan dalam waktu polinomial.
Joshua Grochow