Complexité de la récupération d'une matrice d'adjacence à partir de son carré

Je m'intéresse au problème suivant: étant donné une matrice , y a-t-il un graphe non orienté sur sommets dont la matrice d'adjacence au carré est cette matrice? $n\times n$ $n$

La complexité de calcul de ce problème est-elle connue?

Remarques:

Bien sûr, cela peut aussi être formulé comme un problème de recherche, où l'on vous donne la matrice pour une matrice d'adjacence d'un graphe non orienté et le problème est de trouver n'importe quelle matrice d'adjacence (d'un graphe non orienté) telle que . $A^2$ $A$ $B$ $B^2 = A^2$
Motwani et Soudan ( Calculer les racines des graphiques est difficile , 1994) et Kutz ( La complexité du calcul des racines de la matrice booléenne , 2004) montrent que les problèmes similaires mais distincts de celui-ci sont NP-difficiles - ils ne considèrent que le carré des matrices d'adjacence sous la matrice booléenne multiplication.

cc.complexity-theory graph-theory Ben Fish
la source

Le problème revient à décider de l'existence de

vecteurs avec des produits intérieurs donnés par paires.

n

$n$

Mohammad Al-Turkistany

Très récemment, il y avait un article traitant de cette question pour les matrices stochastiques plutôt que pour les matrices d'adjacence ( arxiv.org/abs/1411.7380 ). La propriété d'être un carré dans ce contexte est connue sous le nom de divisibilité et se révèle être NP-complète dans l'article que j'ai mentionné.

Māris Ozols

@ MohammadAl-Turkistany comment sont-ils équivalents? La solution au problème d'OP nécessite une structure supplémentaire par rapport aux vecteurs génériques (valeur entière, certains indices doivent être nuls, etc.).

Jeremy Kun

Cela devrait être lié à la vérification si une séquence de degrés est graphique. Notez que dans

la diagonale représente la séquence de degrés et

le nombre de voisins communs des sommets

. Il s'agit donc d'une restriction au problème de la séquence des degrés graphiques. Je ne sais pas comment le résoudre.

A^{2}

$A^2$

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

$(A^2)_{ij}$

i, j

$i,j$

SamiD

Réponses:

Il est connu que les carrés des graphes bipartis peuvent être reconnus en temps polynomial (voir ceci ). En général, il y a une caractérisation de la complexité de ce problème basée sur la circonférence du graphique sous-jacent.

Récemment , il y avait une optimisation variante étudiée, ce qui donne des algorithmes pour le problème FPT quand vous voulez tester si un graphe a une racine carrée avec au plus (respectivement au moins) bords pour certains donné entier . $s$ $s$

Nikhil
la source

Merci pour la réponse, mais les résultats que vous mentionnez ne sont pas pertinents pour ce problème - ils supposent, comme dans l'article de Motwani et du Soudan, que la matrice donnée est une matrice de contiguïté et le but est de trouver un autre graphique dont la matrice de contiguïté au carré sous La multiplication matricielle booléenne est la matrice donnée. Alors que dans ce problème ce n'est pas une multiplication booléenne, mais une matrice entière. En d'autres termes, ce problème ne concerne pas la racine carrée d'un graphique car ils utilisent le terme.

Ben Fish

@BenFish Oups. Vous avez mal compris votre question. Pour les matrices entières, je ne vois pas de meilleure façon que d'approcher simplement la racine carrée de la matrice, bien que je suppose que vous êtes intéressé à calculer cela comme la racine carrée d'un graphique pondéré (et je n'ai aucune idée de la façon de le faire)

Nikhil

@Nikhil, la racine carrée d'une matrice n'est pas unique, donc cela ne résout pas la question

Lev Reyzin

@LevReyzin Vous avez raison. En général, je pense que l'unicité peut être caractérisée à partir du spectre de la matrice (peut-être qu'ils ne fournissent pas une condition nécessaire et suffisante). Il existe des résultats intéressants connus pour les matrices stochastiques - Voir eprints.ma.man.ac.uk/1241/01/covered/MIMS_ep2009_21.pdf

Nikhil

Si le graphe sous-jacent est un graphe aléatoire clairsemé, on peut résoudre le problème de la "racine carrée du graphe" en temps polynomial; cela est également vrai pour les graphiques pondérés. Des exemples d'articles qui utilisent cette idée sont Trouver des communautés qui se chevauchent dans les réseaux sociaux et des limites prouvables pour l'apprentissage de certaines représentations profondes . Une idée sur des algorithmes similaires pour les racines de cube graphique, les quatrième racines, etc.?

Pratik
la source