<p>The problem is equivalent to determining is there two equal rows in graph matrix.
We can construct trie on rows of graph matrix. Time compleixty will be O(n^2)</p>

CC BY-SA 4.0
2021-12-18T23:36:08.117Z
@RaduGRIGore the lists have to be sorted, hence it takes $\mathcal{O}(n + m\log n)$
Labo
CC BY-SA 4.0
2021-12-19T20:36:14.843Z
@Labo Thanks for the correction!
Radu GRIGore
CC BY-SA 2.5
2011-01-10T14:08:23.283Z
The same idea on adjacency lists gives $O(m+n)$.
Radu GRIGore
CC BY-SA 2.5
2011-01-10T14:15:22.080Z
Now I'm nuking a fly ;)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-11T18:35:51.910Z
This can be generalised somewhat. If we rephrase the problem as "Given $f : X -> Y$ (where here $f(x) := N(x)$) find distinct $x_1$, $x_2$ such that $f(x_1) = f(x_2)$" then for totally ordered $Y$ one approach is to evaluate $f(x)$ for each $x \in X$, sort them, and check the sorted list for duplicates. The trie is effectively radix sort.
Peter Taylor
CC BY-SA 2.5
2011-01-10T14:02:20.327Z
2011-01-10T14:02:20.327Z
MikleB
<p>EDIT: the solutions by @MikleB and @Travis are much clever. Sorry for the overkilling answer.</p>

<hr>

<p>It seems that the problem can be reduced to the <strong>matrix multiplication problem</strong> on the adjacency matrix $A$ of the graph, by replacing multiplication with EQU (that is, NXOR) and addition with AND. So if there is a pair of twins in the graph, then the resulting matrix $AA^T$ will not be the identity matrix, and the indices $(i,j)$ where the value $a_{i,j}$ is not zero are exactly the twin pair nodes.</p>

<p>To my best knowledge the matrix multiplication problem can be solved in $O(n^\alpha)$ time with $\alpha \approx 2.376$ by the <a href="http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm" rel="nofollow">Coppersmith–Winograd algorithm</a>. If practical solutions are needed, any matrix multiplication algorithms works well in practice are nice. </p>

CC BY-SA 2.5
2011-01-10T12:14:34.240Z
Awesome this works! :D I think it will suffice to evaluate only upper half of the $A^2$. what do you think?
Pratik Deoghare
CC BY-SA 2.5
2011-01-10T12:16:01.167Z
@TheMachineCharmer: Thank you :) Yes, if the graph is undirected.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-10T12:17:57.997Z
Yes. Exactly! :)
Pratik Deoghare
CC BY-SA 2.5
2011-01-10T11:59:12.873Z
2011-01-10T14:18:39.347Z
2011-01-10T14:18:39.347Z
Hsien-Chih Chang 張顯之
<p>This thread is old and OP's question has been answered but I'd like to add another algorithm to find all such pairs in linear time. Nobody mentioned <em>Partition Refinement</em>!</p>

<p>This algorithm finds the equivalence classes of false twins. The algorithm relies on an efficient procedure that refines a partition. Given a set <code>S</code> and a partition <code>P = {X1, ..., Xn}</code>. <code>refine(P, S) = {X1 ^ S, X1 - S, X2 ^ S, X2 - S, ..., Xn ^ S, Xn - S}</code>. <code>^</code> denotes set intersection and <code>-</code> set difference. A partition is stable if it cannot be further refined. This procedure takes time O(|S|) (see Wikipedia's article on partition refinement), so it's fast.</p>

<pre><code>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
</code></pre>

<p>Total time is O(|V|+|E|). This is simple to program as well.</p>

CC BY-SA 4.0
2020-04-07T18:32:02.123Z
This answer should have much more upvotes
Labo
CC BY-SA 3.0
2014-12-05T21:30:20.437Z
2014-12-05T21:30:20.437Z
mrk
<p>Because of the crazy system on this site I can't comment directly, but I have a couple of observations on existing answers.</p>

<p>I'm pretty sure Hsien-Chih Chang's solution needs to correct $A^2$ to $AA^T$.</p>

<p>TheMachineCharmer's observation 4 is back to front (counter-example: [0,0,1],[0,1,0],[0,1,1] has determinant 0 but no twins). If twins exist then the determinant is zero.</p>

CC BY-SA 2.5
2011-01-10T13:26:20.463Z
I see no problem with $A^2$. Any examples? btw, system on this site is NOT crazy! :)
Pratik Deoghare
CC BY-SA 2.5
2011-01-10T13:50:53.470Z
$A^2$ would work for undirected graphs (for which $A$ == $A^T$) but not, in general, for directed graphs. The AND over XNOR needs to compare two rows of A, and matrix multiplication operates on a row from the first matrix with a column from the second.
Peter Taylor
CC BY-SA 2.5
2011-01-10T15:16:54.903Z
System may not be crazy, but perhaps counterintuitive to first time posters.  You can answer but not comment... but your comments were nice enough IMHO to justify posting.  Once you've built up more reputation I think you'll find the system pretty addictive.
hardmath
CC BY-SA 2.5
2011-01-11T18:31:21.323Z
Being able to answer but not comment *is* crazy. It forces new users to choose between not being helpful or answering in the wrong place.
Peter Taylor
CC BY-SA 2.5
2011-01-10T13:12:54.207Z
2011-01-10T13:51:48.713Z
2011-01-10T13:51:48.713Z
Peter Taylor
<p>This thread is quite old; however, nobody seems to have hit on the most elegant and simple approach. Lexicographically sort the adjacency-list in O(n+m) time then check for duplicates (see Aho, Hopcroft, Ullman, 74').  You can use modular decomposition, but this is total overkill.</p>

CC BY-SA 4.0
2020-04-07T18:55:40.370Z
How do you sort the nodes by adjacency list in O(n+m)? I think radix sort on the sorted adjacency lists gives something like O(n * D) with D the maximal degree.
Labo
CC BY-SA 3.0
2014-01-07T04:14:57.517Z
2014-01-07T04:14:57.517Z
Nathan Lindzey
<p>Some observations that might help</p>

<ol>
<li><p>For $a,b \in V$ if $a$ is not twin of $b$ then $c$ and $d$ can't be twins where  $c \in N(a)$ and $d \in N(b)$.</p></li>
<li><p>$|N(a)| \neq |N(b)|$ then $a$ and $b$ can't be twins.</p></li>
<li><p>If $b \in N(a)$ then $a$ and $b$ can't be twins. This works only if you are looking for non-adjacent twins.</p></li>
<li><p>If twins exist then determinant of the adjacency matrix is zero. </p></li>
</ol>

<p><strong>Fancy idea:</strong></p>

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

<p><strike>Stolen from</strike> Inspired by Huffman compression algorithm! :)</p>

CC BY-SA 2.5
2011-01-10T13:05:28.080Z
The 3rd point is true only if we look for _non-adjacent twins_. In the usual notion of _twins_, $a$ and $b$ are allowed to be adjacent.
Mathieu Chapelle
CC BY-SA 2.5
2011-01-10T13:21:33.527Z
Peter Taylor, Mathieu Chapelle: Thanks! I have edited the answer to reflect the changes. @Serge Gaspers: I guess in that case the condition must be $N(a)-{b} = N(b) -{a}$.
Pratik Deoghare
CC BY-SA 2.5
2011-01-10T12:07:56.740Z
2011-01-10T14:12:07.443Z
2011-01-10T14:12:07.443Z
Pratik Deoghare
<p>Twins in a graph are just modules of size 2. The modular decomposition of a graph can be found in $O(n+m)$ time. The modular decomposition tree implicitly represents all modules of the graph and consists of three types of internal nodes: series, parallel and prime nodes, and the leaves consists of the individual nodes. A set of at least two vertices $S \subset V$ is a module if and only if it is some node in the tree or the union of some set of children of a series or a parallel node.</p>

<p>So to find a pair of twin nodes, if they exist, we can construct the modular decomposition tree in $O(n+m)$ time. Then look at the leaves, if the parent of any leaf is a series or parallel node then that node must have at least two children which form a twin pair. So the total running time is linear.</p>

<p><a href="http://en.wikipedia.org/wiki/Modular_decomposition">http://en.wikipedia.org/wiki/Modular_decomposition</a></p>

CC BY-SA 2.5
2011-01-11T10:34:01.460Z
Thank you, also for introducing me to Modular Decomposition!
gphilip
CC BY-SA 2.5
2011-01-10T14:02:39.403Z
2011-01-10T14:02:39.403Z
Travis Service
<p>Let $G=(V,E)$ be a graph. For a vertex $x\in V$, define $N(x)$ to be the (open) neighbourhood of $x$ in $G$. That is, $N(x)=\{y\in V \,\vert\, \{x,y\}\in E\}$. Define two vertices $u,v$ in $G$ to be <em>twins</em> if $u$ and $v$ have the same set of neighbours, that is, if $N(u)=N(v)$.</p>

<blockquote>
  <p>Given a graph $G$ on $n$ vertices and $m$ edges as input, how fast can we find a pair of twins in $G$, if such a pair exists?</p>
</blockquote>

<p>We can check whether two given vertices are twins in $O(n)$ time, by comparing their neighbourhoods. A straightforward algorithm is to find twins is thus to check, for each pair of vertices, whether they are twins. This takes $O(n^{3})$ time (and also finds <em>all</em> pairs of twins). Is there is significantly faster way to find (if there exists) a pair of twins in the graph? Is there known work in the literature that addresses this problem?</p>

CC BY-SA 2.5
2011-01-10T12:50:35.017Z
You could iterate thru neighborhoods and add them to a hashtable. Related: http://cstheory.stackexchange.com/q/3390/236
Radu GRIGore
CC BY-SA 2.5
2011-01-10T13:36:40.997Z
This is exercise 2.17 here http://books.google.co.uk/books?id=RrtXSKMAmWgC&lpg=PA20&ots=yGpYE98tRU&dq=graph%20twin%20vertices&pg=PA29#v=onepage&q&f=false
Radu GRIGore
CC BY-SA 2.5
2011-01-10T14:09:57.523Z
Someone with edit powers should fix the definition of twins. (See the comments on TheMachineCharmer's answer, or the the definition in the book I linked.)
Radu GRIGore
<ds.algorithms><reference-request><graph-algorithms>
Finding twin vertices in graphs
gphilip
# Finding twin vertices in graphs

(Asked by: username_0 on 2011-01-10)

Let $G=(V,E)$ be a graph. For a vertex $x\in V$, define $N(x)$ to be the (open) neighbourhood of $x$ in $G$. That is, $N(x)=\{y\in V \,\vert\, \{x,y\}\in E\}$. Define two vertices $u,v$ in $G$ to be *twins* if $u$ and $v$ have the same set of neighbours, that is, if $N(u)=N(v)$.

> Given a graph $G$ on $n$ vertices and $m$ edges as input, how fast can we find a pair of twins in $G$, if such a pair exists?

We can check whether two given vertices are twins in $O(n)$ time, by comparing their neighbourhoods. A straightforward algorithm is to find twins is thus to check, for each pair of vertices, whether they are twins. This takes $O(n^{3})$ time (and also finds *all* pairs of twins). Is there is significantly faster way to find (if there exists) a pair of twins in the graph? Is there known work in the literature that addresses this problem?

**Tags:** ds.algorithms, reference-request, graph-algorithms

> **Comments:**
> **username_1**: You could iterate thru neighborhoods and add them to a hashtable. Related: http://cstheory.stackexchange.com/q/3390/236  
> **username_1**: This is exercise 2.17 here http://books.google.co.uk/books?id=RrtXSKMAmWgC&lpg=PA20&ots=yGpYE98tRU&dq=graph%20twin%20vertices&pg=PA29#v=onepage&q&f=false  
> **username_1**: Someone with edit powers should fix the definition of twins. (See the comments on TheMachineCharmer's answer, or the the definition in the book I linked.)  

---

## 7 answers

### Answer by username_11 on 2011-01-10. Score: 21 | Accepted answer

Twins in a graph are just modules of size 2. The modular decomposition of a graph can be found in $O(n+m)$ time. The modular decomposition tree implicitly represents all modules of the graph and consists of three types of internal nodes: series, parallel and prime nodes, and the leaves consists of the individual nodes. A set of at least two vertices $S \subset V$ is a module if and only if it is some node in the tree or the union of some set of children of a series or a parallel node.

So to find a pair of twin nodes, if they exist, we can construct the modular decomposition tree in $O(n+m)$ time. Then look at the leaves, if the parent of any leaf is a series or parallel node then that node must have at least two children which form a twin pair. So the total running time is linear.

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

> **Comments:**
> **username_0**: Thank you, also for introducing me to Modular Decomposition!  

---

### Answer by username_2 on 2011-01-10. Score: 12

The problem is equivalent to determining is there two equal rows in graph matrix.
We can construct trie on rows of graph matrix. Time compleixty will be O(n^2)

> **Comments:**
> **username_1**: The same idea on adjacency lists gives $O(m+n)$.  
> **username_4**: Now I'm nuking a fly ;)  
> **username_5**: This can be generalised somewhat. If we rephrase the problem as "Given $f : X -> Y$ (where here $f(x) := N(x)$) find distinct $x_1$, $x_2$ such that $f(x_1) = f(x_2)$" then for totally ordered $Y$ one approach is to evaluate $f(x)$ for each $x \in X$, sort them, and check the sorted list for duplicates. The trie is effectively radix sort.  
> **username_3**: @RaduGRIGore the lists have to be sorted, hence it takes $\mathcal{O}(n + m\log n)$  
> **username_1**: @username_3 Thanks for the correction!  

---

### Answer by username_4 on 2011-01-10. Score: 8

EDIT: the solutions by @username_2 and @Travis are much clever. Sorry for the overkilling answer.

---

It seems that the problem can be reduced to the **matrix multiplication problem** on the adjacency matrix $A$ of the graph, by replacing multiplication with EQU (that is, NXOR) and addition with AND. So if there is a pair of twins in the graph, then the resulting matrix $AA^T$ will not be the identity matrix, and the indices $(i,j)$ where the value $a\_{i,j}$ is not zero are exactly the twin pair nodes.

To my best knowledge the matrix multiplication problem can be solved in $O(n^\alpha)$ time with $\alpha \approx 2.376$ by the [Coppersmith–Winograd algorithm](http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm). If practical solutions are needed, any matrix multiplication algorithms works well in practice are nice.

> **Comments:**
> **username_6**: Awesome this works! :D I think it will suffice to evaluate only upper half of the $A^2$. what do you think?  
> **username_4**: @TheMachineCharmer: Thank you :) Yes, if the graph is undirected.  
> **username_6**: Yes. Exactly! :)  

---

### Answer by username_7 on 2014-12-05. Score: 5

This thread is old and OP's question has been answered but I'd like to add another algorithm to find all such pairs in linear time. Nobody mentioned Partition Refinement!
This algorithm finds the equivalence classes of false twins. The algorithm relies on an efficient procedure that refines a partition. Given a set S and a partition P = {X1, ..., Xn}. refine(P, S) = {X1 ^ S, X1 - S, X2 ^ S, X2 - S, ..., Xn ^ S, Xn - S}. ^ denotes set intersection and - set difference. A partition is stable if it cannot be further refined. This procedure takes time O(|S|) (see Wikipedia's article on partition refinement), so it's fast.
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

Total time is O(|V|+|E|). This is simple to program as well.

> **Comments:**
> **username_3**: This answer should have much more upvotes  

---

### Answer by username_5 on 2011-01-10. Score: 5

Because of the crazy system on this site I can't comment directly, but I have a couple of observations on existing answers.

I'm pretty sure Hsien-Chih Chang's solution needs to correct $A^2$ to $AA^T$.

TheMachineCharmer's observation 4 is back to front (counter-example: [0,0,1],[0,1,0],[0,1,1] has determinant 0 but no twins). If twins exist then the determinant is zero.

> **Comments:**
> **username_6**: I see no problem with $A^2$. Any examples? btw, system on this site is NOT crazy! :)  
> **username_5**: $A^2$ would work for undirected graphs (for which $A$ == $A^T$) but not, in general, for directed graphs. The AND over XNOR needs to compare two rows of A, and matrix multiplication operates on a row from the first matrix with a column from the second.  
> **username_8**: System may not be crazy, but perhaps counterintuitive to first time posters.  You can answer but not comment... but your comments were nice enough IMHO to justify posting.  Once you've built up more reputation I think you'll find the system pretty addictive.  
> **username_5**: Being able to answer but not comment *is* crazy. It forces new users to choose between not being helpful or answering in the wrong place.  

---

### Answer by username_9 on 2014-01-07. Score: 4

This thread is quite old; however, nobody seems to have hit on the most elegant and simple approach. Lexicographically sort the adjacency-list in O(n+m) time then check for duplicates (see Aho, Hopcroft, Ullman, 74'). You can use modular decomposition, but this is total overkill.

> **Comments:**
> **username_3**: How do you sort the nodes by adjacency list in O(n+m)? I think radix sort on the sorted adjacency lists gives something like O(n * D) with D the maximal degree.  

---

### Answer by username_6 on 2011-01-10. Score: 1

Some observations that might help

1. For $a,b \in V$ if $a$ is not twin of $b$ then $c$ and $d$ can't be twins where $c \in N(a)$ and $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! :)

> **Comments:**
> **username_10**: The 3rd point is true only if we look for _non-adjacent twins_. In the usual notion of _twins_, $a$ and $b$ are allowed to be adjacent.  
> **username_6**: username_5, username_10: Thanks! I have edited the answer to reflect the changes. @Serge Gaspers: I guess in that case the condition must be $N(a)-{b} = N(b) -{a}$.  

---

