Complejidad de la recuperación de una matriz de adyacencia de su cuadrado

Estoy interesado en el siguiente problema: Dada una matriz , ¿hay un gráfico no dirigido en vértices cuya matriz de adyacencia al cuadrado es esa matriz? $n\times n$ $n$

¿Se conoce la complejidad computacional de este problema?

Observaciones:

Por supuesto, esto también puede expresarse como un problema de búsqueda, donde se le da a la matriz para una matriz de adyacencia de un gráfico no dirigido y el problema es encontrar cualquier matriz de adyacencia (de un gráfico no dirigido) tal que . $A^2$ $A$ $B$ $B^2 = A^2$
Motwani y Sudán ( Calcular las raíces de los gráficos es difícil , 1994) y Kutz ( La complejidad del cálculo de la raíz de la matriz booleana , 2004) muestran problemas similares pero distintos de este son NP-difícil: consideran solo el cuadrado de las matrices de adyacencia bajo la matriz booleana multiplicación.

cc.complexity-theory graph-theory Ben Fish
fuente

El problema es equivalente a decidir la existencia de

vectores con productos internos por pares dados.

n

$n$

Mohammad Al-Turkistany

Muy recientemente hubo un documento que abordaba esta cuestión para las matrices estocásticas en lugar de las matrices de adyacencia ( arxiv.org/abs/1411.7380 ). La propiedad de ser un cuadrado en este contexto se conoce como divisibilidad y se muestra que tiene NP completo en el artículo que mencioné.

Māris Ozols

@ MohammadAl-Turkistany ¿cómo son equivalentes? La solución al problema de OP requiere una estructura adicional que los vectores genéricos (valor entero, ciertos índices deben ser cero, etc.).

Jeremy Kun

Esto debería estar relacionado con la comprobación de si una secuencia de grados es gráfica. Observe que en

la diagonal representa la secuencia de grados y

el número de vecinos comunes de vértices

. Por lo tanto, es una restricción al problema de secuencia de grados gráficos. Sin embargo, no tengo idea de cómo resolverlo.

A^{2}

$A^2$

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

$(A^2)_{ij}$

i, j

$i,j$

SamiD

Respuestas:

Se sabe que los cuadrados de los gráficos bipartitos se pueden reconocer en el tiempo polinómico (ver esto ). En general, existe una caracterización de la complejidad de este problema basada en la circunferencia del gráfico subyacente.

$s$ $s$

Nikhil
fuente

Gracias por la respuesta, pero los resultados que menciona no son relevantes para este problema: suponen, como en el artículo de Motwani y Sudán, que la matriz dada es una matriz de adyacencia y el objetivo es encontrar otro gráfico cuya matriz de adyacencia esté al cuadrado debajo La multiplicación de matriz booleana es la matriz dada. Mientras que en este problema no es booleano, sino multiplicación de matriz entera. En otras palabras, este problema no se trata de la raíz cuadrada de un gráfico, ya que usan el término.

Ben Fish

@BenFish Oops. Mal entendido su pregunta. Para las matrices enteras, no veo una mejor manera que solo aproximar la raíz cuadrada de la matriz, aunque supongo que está interesado en calcular esto como la raíz cuadrada de un gráfico ponderado (y no tengo idea de cómo hacerlo)

Nikhil

@Nikhil la raíz cuadrada de una matriz no es única, por lo que hacer esto no resuelve la pregunta

Lev Reyzin

@LevReyzin Estás en lo correcto. En general, creo que la singularidad se puede caracterizar a partir del espectro de la matriz (tal vez no proporcionan una condición necesaria y suficiente). Hay algunos resultados interesantes conocidos para las matrices estocásticas: consulte eprints.ma.man.ac.uk/1241/01/covered/MIMS_ep2009_21.pdf

Nikhil

Si el gráfico subyacente es un gráfico escaso y aleatorio, se puede resolver el problema de la "raíz cuadrada del gráfico" en tiempo polinómico; Esto también es cierto para los gráficos ponderados. Ejemplos de documentos que usan esta idea son Encontrar comunidades superpuestas en redes sociales y límites demostrables para aprender algunas representaciones profundas . ¿Alguna idea sobre algoritmos similares para raíces cuadradas gráficas, raíces cuarta, etc.?

Pratik
fuente