Kompleksitas pemulihan matriks adjacency dari kuadratnya

Saya tertarik masalah berikut: Mengingat matriks, apakah ada sebuah grafik diarahkan pada simpul yang adjacency matrix kuadrat yaitu bahwa matriks? $n\times n$ $n$

Apakah kompleksitas komputasi dari masalah ini diketahui?

Catatan:

Tentu saja ini juga dapat diutarakan sebagai masalah pencarian, di mana Anda diberi matriks untuk matriks adjacency dari grafik yang tidak terarah dan masalahnya adalah menemukan matriks adjacency (dari grafik yang tidak diarahkan) sedemikian rupa sehingga . $A^2$ $A$ $B$ $B^2 = A^2$
Motwani dan Sudan ( Komputasi akar grafik sulit , 1994) dan Kutz ( Kompleksitas perhitungan akar matriks Boolean , 2004) menunjukkan masalah yang sama tetapi berbeda dari yang ini adalah NP-keras - mereka menganggap hanya kuadrat dari matriks kedekatan di bawah matriks Boolean perkalian.

cc.complexity-theory graph-theory Ben Fish
sumber

Masalahnya setara dengan memutuskan keberadaan

vektor dengan produk dalam yang diberikan berpasangan.

n

$n$

Mohammad Al-Turkistany

Baru-baru ini ada makalah yang membahas pertanyaan ini untuk matriks stokastik daripada matriks kedekatan ( arxiv.org/ab/1411.7380 ). Properti menjadi kotak dalam konteks ini dikenal sebagai dapat dibagi dan ditampilkan sebagai NP-lengkap dalam makalah yang saya sebutkan.

Māris Ozols

@ MohammadAl-Turkistany bagaimana mereka setara? Solusi untuk masalah OP memerlukan struktur tambahan daripada vektor generik (nilai integer, indeks tertentu harus nol, dll).

Jeremy Kun

Ini harus dikaitkan dengan memeriksa apakah urutan derajat grafis. Perhatikan bahwa pada

diagonal mewakili deret derajat dan

jumlah tetangga simpul yang sama

. Jadi itu adalah batasan untuk masalah urutan derajat grafis. Tidak tahu bagaimana menyelesaikannya.

A^{2}

$A^2$

(A^{2})_{i j}

$(A^2)_{ij}$

i, j

$i,j$

SamiD

Jawaban:

Diketahui bahwa kuadrat dari grafik bipartit dapat dikenali dalam waktu polinomial (Lihat ini ). Secara umum, ada karakterisasi dari kompleksitas masalah ini berdasarkan pada ketebalan grafik yang mendasarinya.

Baru-baru ini ada optimasi varian dipelajari, yang memberikan algoritma FPT untuk masalah ketika Anda ingin menguji apakah grafik memiliki akar kuadrat dengan paling banyak (masing-masing setidaknya) tepi untuk beberapa diberikan bilangan bulat . $s$ $s$

Nikhil
sumber

Terima kasih atas tanggapannya, tetapi hasil yang Anda sebutkan tidak relevan dengan masalah ini - mereka menganggap, seperti dalam makalah Motwani dan Sudan, bahwa matriks yang diberikan adalah matriks adjacency dan tujuannya adalah untuk menemukan grafik lain yang matriks adjacencynya dikuadratkan di bawah Multiplikasi matriks Boolean adalah matriks yang diberikan. Padahal dalam masalah ini bukan Boolean, tetapi perkalian matriks integer. Dengan kata lain, masalah ini bukan tentang akar kuadrat dari grafik karena mereka menggunakan istilah tersebut.

Ben Fish

@BenFish Ups. Disalahpahami pertanyaan Anda. Untuk matriks Integer, saya tidak melihat cara yang lebih baik daripada hanya mendekati akar kuadrat dari matriks, meskipun saya menganggap Anda tertarik untuk menghitung ini sebagai akar kuadrat dari grafik berbobot (dan saya tidak tahu bagaimana melakukannya)

Nikhil

@ Nikhil akar kuadrat dari sebuah matriks tidak unik, jadi melakukan ini tidak menyelesaikan pertanyaan

Lev Reyzin

@LevReyzin Anda benar. Secara umum, saya pikir keunikan dapat dicirikan dari spektrum matriks (mungkin mereka tidak menyediakan kondisi yang diperlukan dan cukup). Ada beberapa hasil menarik yang dikenal untuk matriks stokastik - Lihat eprints.ma.man.ac.uk/1241/01/covered/MIMS_ep2009_21.pdf

Nikhil

Jika grafik yang mendasarinya adalah grafik acak jarang, seseorang dapat memecahkan masalah "graph square root" dalam waktu polinomial; ini juga berlaku untuk grafik berbobot. Contoh makalah yang menggunakan ide ini adalah Menemukan Komunitas yang Tumpang tindih di Jejaring Sosial dan Batas Terbukti untuk Mempelajari Beberapa Representasi Mendalam . Adakah gagasan tentang algoritme yang serupa untuk akar pangkat tiga, akar keempat, dll.?

Pratik
sumber