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