Złożoność odzyskiwania macierzy sąsiedztwa z jej kwadratu

Interesuje mnie następujący problem: Biorąc pod uwagę macierz , czy istnieje niekierowany wykres na wierzchołkach, których macierz przylegania do kwadratu jest tą macierzą? $n\times n$ $n$

Czy znana jest złożoność obliczeniowa tego problemu?

Uwagi:

Oczywiście może być również sformułowany jako problem wyszukiwania, w którym podane są macierzy do macierz przylegania o nieukierunkowane przebiegu, problem polega na znalezieniu żadnej matrycy przylegania (o nieukierunkowane wykresu) takie, że . $A^2$ $A$ $B$ $B^2 = A^2$
Motwani i Sudan ( Obliczanie pierwiastków grafów jest trudne , 1994) i Kutz ( Złożoność obliczania pierwiastków macierzy Boolean , 2004) wykazują podobne, ale wyraźne problemy z tym, że są trudne NP - biorą pod uwagę tylko kwadrat macierzy przylegania w macierzy Boolean mnożenie.

cc.complexity-theory graph-theory Ben Fish
źródło

Problem jest równoważny z decydowaniem o istnieniu

wektorów z danymi parami produktów wewnętrznych.

n

$n$

Mohammad Al-Turkistany

Niedawno pojawił się artykuł na ten temat dotyczący matryc stochastycznych zamiast macierzy przylegania ( arxiv.org/abs/1411.7380 ). Właściwość bycia kwadratem w tym kontekście jest znana jako podzielność i wykazano, że jest NP-zupełna we wspomnianym artykule.

Māris Ozols,

@ MohammadAl-Turkistany, w jaki sposób są one równoważne? Rozwiązanie problemu OP wymaga dodatkowej struktury niż wektory ogólne (wartości całkowite, niektóre wskaźniki muszą wynosić zero itp.).

Jeremy Kun,

Powinno to być związane ze sprawdzaniem, czy sekwencja stopni jest graficzna. Należy zauważyć, że w

przekątnej przedstawia sekwencję stopień i

liczbę wspólnych sąsiadów wierzchołków

. Jest to zatem ograniczenie problemu z sekwencją stopni graficznych. Nie mam pojęcia, jak to rozwiązać.

A^{2}

$A^2$

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

$(A^2)_{ij}$

i, j

$i,j$

SamiD

Odpowiedzi:

Wiadomo, że kwadraty wykresów dwustronnych można rozpoznać w czasie wielomianowym (zobacz to ). Ogólnie rzecz biorąc, charakterystyka złożoności tego problemu oparta jest na obwodzie leżącego u jego podstaw wykresu.

Ostatnio nastąpiła optymalizacja wariant badane, co daje FPT algorytmy dla problemu, gdy chcesz sprawdzić, czy wykres ma pierwiastek kwadratowy z co najwyżej (odpowiednio co najmniej) krawędziach dla niektórych podana liczba całkowita . $s$ $s$

Nikhil
źródło

Dziękuję za odpowiedź, ale wyniki, o których wspomniałeś, nie mają związku z tym problemem - zakładają, podobnie jak w pracy Motwani i Sudanu, że dana macierz jest macierzą przylegania, a celem jest znalezienie innego wykresu, którego macierz przylegania wyrównała się pod Mnożenie macierzy logicznej to podana macierz. Tymczasem w tym problemie nie chodzi o wartość logiczną, lecz o mnożenie macierzy całkowitych. Innymi słowy, ten problem nie dotyczy pierwiastka kwadratowego wykresu, ponieważ używają tego terminu.

Ben Fish

@BenFish Ups. Nie zrozumiałem twojego pytania. W przypadku macierzy całkowitych nie widzę lepszego sposobu niż tylko przybliżenie pierwiastka kwadratowego macierzy, ale przypuszczam, że jesteś zainteresowany obliczeniem tego jako pierwiastka kwadratowego z ważonego wykresu (i nie mam pojęcia, jak to zrobić)

Nikhil,

@Nikhil pierwiastek kwadratowy z macierzy nie jest unikalny, więc zrobienie tego nie rozwiązuje pytania

Lev Reyzin

@LevReyzin Masz rację. Ogólnie myślę, że wyjątkowość można scharakteryzować na podstawie widma matrycy (być może nie zapewniają one koniecznego i wystarczającego warunku). Istnieje kilka interesujących wyników znanych z matryc stochastycznych - patrz eprints.ma.man.ac.uk/1241/01/covered/MIMS_ep2009_21.pdf

Nikhil

Jeśli wykres leżący u podstaw jest rzadkim, losowym wykresem, można rozwiązać problem „pierwiastka z grafu” w czasie wielomianowym; dotyczy to również wykresów ważonych. Przykłady artykułów, które wykorzystują ten pomysł, to: Znajdowanie nakładających się społeczności w sieciach społecznościowych i możliwych granic do nauki pewnych głębokich reprezentacji . Masz pomysł na podobne algorytmy dla pierwiastków grafowych, czwartych pierwiastków itp.?

Pratik
źródło