Нахождение вершин-близнецов в графах

Пусть $G=(V,E)$ - граф. Для вершины $x\in V$ , определим $N(x)$ , чтобы быть (открытая) окрестность $x$ в $G$ . То есть $N(x)=\{y\in V \,\vert\, \{x,y\}\in E\}$ . Определим две вершины$u,v$ в$G$ какдвойники,если$u$ и$v$ имеют одинаковый набор соседей, то есть если$N(u)=N(v)$ .

Учитывая граф $G$ на $n$ вершинах и $m$ ребрах в качестве входных данных, как быстро мы можем найти пару близнецов в $G$ , если такая пара существует?

Мы можем проверить, являются ли две данные вершины близнецами за $O(n)$ времени, сравнивая их окрестности. Простой алгоритм состоит в том, чтобы найти близнецов, то есть для каждой пары вершин проверять, являются ли они близнецами. Это занимает $O(n^{3})$ времени (а также находит все пары близнецов). Существует ли значительно более быстрый способ найти (если есть) пару близнецов в графе? Есть ли в литературе известная работа, посвященная этой проблеме?

Близнецы в графе - это просто модули размера 2. Модульная декомпозиция графа может быть найдена за время . Модульное дерево декомпозиции неявно представляет все модули графа и состоит из трех типов внутренних узлов: рядов, параллельных и простых узлов, а листья состоят из отдельных узлов. Набор из по крайней мере двух вершин S ⊂ V является модулем тогда и только тогда, когда он является некоторым узлом в дереве или объединением некоторого набора дочерних элементов ряда или параллельного узла.$O(n+m)$$S \subset V$

Таким образом, чтобы найти пару узлов-близнецов, если они существуют, мы можем построить дерево модульного разложения за времени. Затем посмотрите на листья, если родитель любого листа является последовательным или параллельным узлом, то у этого узла должно быть как минимум два потомка, которые образуют двойную пару. Таким образом, общее время работы является линейным.$O(n+m)$

http://en.wikipedia.org/wiki/Modular_decomposition

Проблема эквивалентна определению, есть ли две равные строки в матрице графа. Мы можем построить три на строках матрицы графа. Время завершения будет O (n ^ 2)

РЕДАКТИРОВАТЬ: решения @MikleB и @Travis намного умнее. Извините за излишний ответ.

Кажется, что эту проблему можно свести к задаче умножения матриц на матрице смежности графа, заменив умножение на EQU (то есть NXOR) и сложение на AND. Таким образом, если в графе есть пара близнецов, то результирующая матрица A A T не будет единичной матрицей, и индексы ( i , j ), где значение a i , j не равно нулю, являются в точности узлами пары пар. ,$A$$AA^T$$(i,j)$$a_{i,j}$

Насколько мне известно, проблема умножения матриц может быть решена за время с α ≈ 2.376 по алгоритму Копперсмита – Винограда . Если нужны практические решения, любые алгоритмы матричного умножения хорошо работают на практике.$O(n^\alpha)$$\alpha \approx 2.376$

Из-за сумасшедшей системы на этом сайте я не могу комментировать напрямую, но у меня есть пара замечаний по поводу существующих ответов.

Я вполне уверен , что потребности решения Сянь-чжи Чанга , чтобы исправить до A A T .$A^2$$AA^T$

Наблюдение 4MachineCharmer задом наперед (контрпример: [0,0,1], [0,1,0], [0,1,1] имеет определитель 0, но без двойников). Если близнецы существуют, то детерминант равен нулю.

Эта тема довольно старая; однако никто, кажется, не использовал самый элегантный и простой подход. Лексикографически сортируйте список смежности по времени O (n + m), затем проверяйте наличие дубликатов (см. Aho, Hopcroft, Ullman, 74 '). Вы можете использовать модульную декомпозицию, но это полный перебор.

Эта ветка старая, и на вопрос OP ответили, но я хотел бы добавить еще один алгоритм, чтобы найти все такие пары за линейное время. Никто не упомянул уточнение разделов !

Этот алгоритм находит классы эквивалентности ложных близнецов. Алгоритм основан на эффективной процедуре, которая уточняет раздел. Дан набор Sи раздел P = {X1, ..., Xn}. refine(P, S) = {X1 ^ S, X1 - S, X2 ^ S, X2 - S, ..., Xn ^ S, Xn - S}, ^обозначает пересечение -множества и разность множества. Раздел стабилен, если его невозможно доработать. Эта процедура занимает время O (| S |) (см. Статью Википедии об уточнении раздела), поэтому она быстрая.

Algorithm:

P = {V} // initial partition consists of the vertex set
for every vertex v:
    P = refine(P, N(v)) // refine with the open neighborhood of v

Общее время O (| V | + | E |). Это также легко программировать.

Некоторые наблюдения, которые могут помочь

1. Для $a,b \in V$ если $a$ не близнец $b$ тогда $c$ а также $d$ не может быть близнецов где $c \in N(a)$ а также $d \in N(b)$.

2. $|N(a)| \neq |N(b)|$ then $a$ and $b$ can't be twins.

3. If $b \in N(a)$ then $a$ and $b$ can't be twins. This works only if you are looking for non-adjacent twins.

4. If twins exist then determinant of the adjacency matrix is zero.

Fancy idea:

1. Build a complete binary tree with height = |V|.
2. Then start reading one row of adjacency matrix.
3. If you encounter 0 take left otherwise take right.
4. When you reach a leaf store your vertex there.
5. Do this for all the rows. So, in the end each leaf will have neighbors.

Stolen from Inspired by Huffman compression algorithm! :)