Сложность восстановления матрицы смежности из ее квадрата

Меня интересует следующая проблема: Имеется ли матрица, существует ли неориентированный граф на вершинах, квадрат матрицы смежности которых является этой матрицей? $n\times n$ $n$

Известна ли вычислительная сложность этой проблемы?

Примечания:

Конечно, это также можно сформулировать как задачу поиска, где вам дается матрица для матрицы смежности неориентированного графа, и задача состоит в том, чтобы найти любую матрицу смежности (неориентированного графа) такую, что . $A^2$ $A$ $B$ $B^2 = A^2$
Мотвани и Судан ( Вычисление корней графов сложно , 1994) и Куц ( Сложность вычисления корня булевой матрицы , 2004) показывают аналогичные, но отличные от этого проблемы - NP-сложные - они рассматривают только квадрат матриц смежности под булевой матрицей умножение.

cc.complexity-theory graph-theory Бен Фиш
источник

Задача эквивалентна решению существования векторов с заданными попарно внутренними произведениями.

n

$n$

Мухаммед Аль-Туркистани

Совсем недавно появилась статья, посвященная этому вопросу для стохастических матриц, а не матриц смежности ( arxiv.org/abs/1411.7380 ). Свойство быть квадратом в этом контексте известно как делимость, и показано, что оно является NP-полным в статье, которую я упомянул.

Марис Озолс

@ MohammadAl-Turkistany как они эквивалентны? Решение проблемы OP требует дополнительной структуры, чем общие векторы (целочисленные значения, некоторые индексы должны быть равны нулю и т. Д.).

Джереми Кун

Это должно быть связано с проверкой, является ли последовательность степеней графической. Обратите внимание, что в

диагональ представляет последовательность степеней, а

- число общих соседей вершин

. Таким образом, это ограничение проблемы последовательности графических степеней. Хотя понятия не имею, как это решить.

A^{2}

$A^2$

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

$(A^2)_{ij}$

i, j

$i,j$

SamiD

Ответы:

Известно, что квадраты двудольных графов можно распознать за полиномиальное время (см. Это ). В общем, есть характеристика сложности этой проблемы, основанная на обхвате основного графа.

Недавно был изучен вариант оптимизации , который дает алгоритмы FPT для задачи, когда вы хотите проверить, имеет ли граф квадратный корень с не более (соответственно не менее) ребрами для некоторого заданного целого числа . $s$ $s$

Нихилу
источник

Спасибо за ответ, но упомянутые вами результаты не имеют отношения к этой проблеме - они предполагают, как и в статье Мотвани и Судана, что данная матрица является матрицей смежности, и цель состоит в том, чтобы найти другой граф, матрица смежности которого возводится в квадрат под Умножение булевой матрицы является заданной матрицей. Тогда как в этой задаче это не булево, а целочисленное умножение матриц. Другими словами, эта проблема не о квадратном корне графа, поскольку они используют термин.

Бен Фиш

@BenFish Упс. Неправильно понял ваш вопрос. Для целочисленных матриц я не вижу лучшего способа, чем просто приближение квадратного корня матрицы, хотя я предполагаю, что вы заинтересованы в том, чтобы вычислить это как квадратный корень из взвешенного графа (и я понятия не имею, как это сделать)

Нихил

@Nikhil квадратный корень из матрицы не уникален, поэтому выполнение этого не решает вопрос

Лев Рейзин

@LevReyzin Вы правы. В целом, я думаю, что уникальность может быть охарактеризована из спектра матрицы (возможно, они не обеспечивают необходимое и достаточное условие). Есть некоторые интересные результаты , известные для случайных матриц - См eprints.ma.man.ac.uk/1241/01/covered/MIMS_ep2009_21.pdf

Нихилу

Если лежащий в основе граф является разреженным, случайным графом, можно решить проблему «квадратного корня графа» за полиномиальное время; это также верно для взвешенных графиков. Примерами статей, использующих эту идею, являются « Поиск перекрывающихся сообществ в социальных сетях» и « Предложенные границы для изучения некоторых глубоких представлений» . Есть идеи о подобных алгоритмах для корней графов, четвертых корней и т. Д.?

Pratik
источник