Complexidade da recuperação de uma matriz adjacente a partir de seu quadrado

Estou interessado no seguinte problema: Dado um matriz, existe um grafo não direcionado em vértices cuja adjacência matriz ao quadrado é essa matriz? $n\times n$ $n$

A complexidade computacional desse problema é conhecida?

Observações:

Obviamente, isso também pode ser formulado como um problema de pesquisa, onde você recebe a matriz para uma matriz de adjacência de um gráfico não direcionado e o problema é encontrar qualquer matriz de adjacência (de um gráfico não direcionado) tal que . $A^2$ $A$ $B$ $B^2 = A^2$
Motwani e Sudão ( computação das raízes dos gráficos é difícil , 1994) e Kutz ( A complexidade da computação da raiz da matriz booleana , 2004) mostram problemas semelhantes, mas distintos, desse problema são difíceis de NP - eles consideram apenas o quadrado das matrizes de adjacência na matriz booleana multiplicação.

cc.complexity-theory graph-theory Ben Fish
fonte

O problema é equivalente a decidir a existência de

vetores com determinados produtos internos em pares.

n

$n$

Mohammad Al-Turkistany

Muito recentemente, houve um trabalho abordando essa questão para matrizes estocásticas em vez de matrizes de adjacência ( arxiv.org/abs/1411.7380 ). A propriedade de ser um quadrado nesse contexto é conhecida como divisibilidade e é mostrada como NP-completa no artigo que mencionei.

Māris Ozols

@ MohammadAl-Turkistany como são equivalentes? A solução para o problema do OP requer estrutura adicional que vetores genéricos (valor inteiro, determinados índices devem ser zero, etc).

Jeremy Kun

Isso deve estar relacionado à verificação se uma sequência de graus é gráfica. Note-se que em

a diagonal representa a sequência de grau e

o número de vizinhos comuns de vértices

. Portanto, é uma restrição ao problema da sequência gráfica de graus. Nenhuma idéia de como resolvê-lo embora.

A^{2}

$A^2$

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

$(A^2)_{ij}$

i, j

$i,j$

samid

Respostas:

Sabe-se que quadrados de gráficos bipartidos podem ser reconhecidos em tempo polinomial (Veja isto ). Em geral, há uma caracterização da complexidade desse problema com base na circunferência do gráfico subjacente.

$s$ $s$

Nikhil
fonte

Obrigado pela resposta, mas os resultados mencionados não são relevantes para esse problema - eles assumem, como no artigo de Motwani e Sudão, que a matriz fornecida é uma matriz adjacente e o objetivo é encontrar outro gráfico cuja matriz adjacente ao quadrado A multiplicação de matrizes booleanas é a matriz fornecida. Considerando que neste problema não é booleano, mas multiplicação de matriz inteira. Em outras palavras, esse problema não se refere à raiz quadrada de um gráfico, pois eles usam o termo.

Ben Peixe

@BenFish Oops. Entendeu mal sua pergunta. Para matrizes inteiras, não vejo uma maneira melhor do que apenas aproximar a raiz quadrada da matriz, embora eu presuma que você esteja interessado em computar isso como a raiz quadrada de um gráfico ponderado (e não tenho idéia de como fazer isso)

Nikhil

@Nikhil a raiz quadrada de uma matriz não é original, assim que fazendo isso não resolver a questão

Lev Reyzin

@LevReyzin Você está correto. Em geral, acho que a singularidade pode ser caracterizada pelo espectro da matriz (talvez eles não forneçam uma condição necessária e suficiente). Há alguns resultados interessantes conhecidos por matrizes estocásticos - Veja eprints.ma.man.ac.uk/1241/01/covered/MIMS_ep2009_21.pdf

Nikhil

Se o gráfico subjacente for um gráfico esparso e aleatório, pode-se resolver o problema da "raiz quadrada do gráfico" em tempo polinomial; isso também é válido para gráficos ponderados. Exemplos de artigos que usam essa idéia são: Encontrar comunidades sobrepostas em redes sociais e limites prováveis para aprender algumas representações profundas . Alguma idéia sobre algoritmos semelhantes para raízes de cubos de grafos, quarta raízes etc.?

Pratik
fonte