Komplexität der Wiederherstellung einer Adjazenzmatrix aus ihrem Quadrat

Ich interessiere mich für das folgende Problem: Gibt es bei einer gegebenen Matrix von einen ungerichteten Graphen auf Eckpunkten, deren Adjazenzmatrix zum Quadrat dieser Matrix passt? $n\times n$ $n$

Ist die rechnerische Komplexität dieses Problems bekannt?

Bemerkungen:

Natürlich kann dies auch als ein Suchproblem formuliert werden, bei dem Sie die Matrix für eine Adjazenzmatrix eines ungerichteten Graphen erhalten und das Problem darin besteht, eine beliebige Adjazenzmatrix (eines ungerichteten Graphen) so zu finden, dass . $A^2$ $A$ $B$ $B^2 = A^2$
Motwani und Sudan ( Berechnen der Wurzeln von Graphen ist schwer , 1994) und Kutz ( Die Komplexität der Booleschen Matrixwurzelberechnung , 2004) zeigen ähnliche, aber unterschiedliche Probleme, die NP-schwer sind - sie berücksichtigen nur das Quadrat der Adjazenzmatrizen unter der Booleschen Matrix Multiplikation.

cc.complexity-theory graph-theory Ben Fish
quelle

Das Problem ist äquivalent zur Entscheidung der Existenz von Vektoren mit gegebenen paarweisen inneren Produkten.

n

$n$

Mohammad Al-Turkistany

Vor kurzem wurde diese Frage eher für stochastische Matrizen als für Adjazenzmatrizen behandelt ( arxiv.org/abs/1411.7380 ). Die Eigenschaft, ein Quadrat zu sein, ist in diesem Zusammenhang als Teilbarkeit bekannt und wird in dem erwähnten Aufsatz als NP-vollständig gezeigt.

Māris Ozols

@ MohammadAl-Turkistany wie sind sie gleichwertig? Die Lösung des OP-Problems erfordert eine zusätzliche Struktur als generische Vektoren (ganzzahlige Werte, bestimmte Indizes müssen Null sein usw.).

Jeremy Kun

Dies sollte mit der Überprüfung zusammenhängen, ob eine Gradfolge grafisch ist. Beachten Sie, dass in die Diagonale die Gradfolge und die Anzahl der gemeinsamen Nachbarn der Eckpunkte . Es handelt sich also um eine Beschränkung auf das Problem der grafischen Gradfolge. Keine Ahnung, wie man es löst.

A^{2}

$A^2$

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

$(A^2)_{ij}$

i, j

$i,j$

SamiD

Antworten:

Es ist bekannt, dass Quadrate von zweigeteilten Graphen in der Polynomzeit erkannt werden können (siehe dies ). Im Allgemeinen wird die Komplexität dieses Problems anhand des Umfangs des zugrunde liegenden Diagramms charakterisiert .

Vor kurzem gab es eine Optimierungsvariante untersucht, die FPT - Algorithmen für das Problem gibt , wenn Sie testen möchten , ob ein Graph , der eine Quadratwurzel hat mit höchstens (jeweils mindestens) Kanten für eine ganze Zahl gegeben . $s$ $s$

Nikhil
quelle

Vielen Dank für die Antwort, aber die Ergebnisse, die Sie erwähnen, sind für dieses Problem nicht relevant - sie gehen, wie im Aufsatz von Motwani und Sudan, davon aus, dass die angegebene Matrix eine Adjazenzmatrix ist und das Ziel darin besteht, ein anderes Diagramm zu finden, dessen Adjazenzmatrix im Quadrat darunter liegt Boolesche Matrixmultiplikation ist die gegebene Matrix. Bei diesem Problem handelt es sich nicht um eine boolesche Multiplikation, sondern um eine Ganzzahlmatrix. Mit anderen Worten, bei diesem Problem geht es nicht um die Quadratwurzel eines Diagramms, wie sie den Begriff verwenden.

Ben Fish

@BenFish Ups. Missverstanden deine Frage. Für Integer-Matrizen gibt es keinen besseren Weg, als die Quadratwurzel der Matrix zu approximieren, obwohl ich davon ausgehe, dass Sie daran interessiert sind, diese als Quadratwurzel eines gewichteten Graphen zu berechnen (und ich habe keine Ahnung, wie Sie das tun sollen).

Nikhil

@ Nikhil die Quadratwurzel einer Matrix ist nicht eindeutig, so dass dies nicht die Frage löst

Lev Reyzin

@ LevReyzin Sie sind richtig. Im Allgemeinen denke ich, dass die Einzigartigkeit anhand des Spektrums der Matrix charakterisiert werden kann (möglicherweise bieten sie keine notwendige und ausreichende Bedingung). Es gibt einige interessante Ergebnisse für stochastische Matrizen - siehe eprints.ma.man.ac.uk/1241/01/covered/MIMS_ep2009_21.pdf

Nikhil

Wenn der zugrunde liegende Graph ein spärlicher Zufallsgraph ist, kann man das Problem der "Graphquadratwurzel" in der Polynomzeit lösen. Dies gilt auch für gewichtete Diagramme. Beispiele für Artikel, die diese Idee verwenden, sind das Auffinden überlappender Gemeinschaften in sozialen Netzwerken und nachweisbare Grenzen für das Erlernen einiger tiefer Repräsentationen . Haben Sie eine Idee zu ähnlichen Algorithmen für Diagrammwürfelwurzeln, vierte Wurzeln usw.?

Pratik
quelle