25
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ You could iterate thru neighborhoods and add them to a hashtable. Related: cstheory.stackexchange.com/q/3390/236 $\endgroup$
    – Radu GRIGore
    Commented Jan 10, 2011 at 12:50
  • 1
    $\begingroup$ This is exercise 2.17 here books.google.co.uk/… $\endgroup$
    – Radu GRIGore
    Commented Jan 10, 2011 at 13:36
  • $\begingroup$ 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.) $\endgroup$
    – Radu GRIGore
    Commented Jan 10, 2011 at 14:09

7 Answers 7

Reset to default
21
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, also for introducing me to Modular Decomposition! $\endgroup$
    – gphilip
    Commented Jan 11, 2011 at 10:34
12
$\begingroup$

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)

Improve this answer
$\endgroup$
5
  • 6
    $\begingroup$ The same idea on adjacency lists gives $O(m+n)$. $\endgroup$
    – Radu GRIGore
    Commented Jan 10, 2011 at 14:08
  • $\begingroup$ Now I'm nuking a fly ;) $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Jan 10, 2011 at 14:15
  • 2
    $\begingroup$ 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. $\endgroup$
    – Peter Taylor
    Commented Jan 11, 2011 at 18:35
  • 1
    $\begingroup$ @RaduGRIGore the lists have to be sorted, hence it takes $\mathcal{O}(n + m\log n)$ $\endgroup$
    – Labo
    Commented Dec 18, 2021 at 23:36
  • $\begingroup$ @Labo Thanks for the correction! $\endgroup$
    – Radu GRIGore
    Commented Dec 19, 2021 at 20:36
8
$\begingroup$

EDIT: the solutions by @MikleB 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. If practical solutions are needed, any matrix multiplication algorithms works well in practice are nice.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Awesome this works! :D I think it will suffice to evaluate only upper half of the $A^2$. what do you think? $\endgroup$
    – Pratik Deoghare
    Commented Jan 10, 2011 at 12:14
  • 1
    $\begingroup$ @TheMachineCharmer: Thank you :) Yes, if the graph is undirected. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Jan 10, 2011 at 12:16
  • $\begingroup$ Yes. Exactly! :) $\endgroup$
    – Pratik Deoghare
    Commented Jan 10, 2011 at 12:17
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I see no problem with $A^2$. Any examples? btw, system on this site is NOT crazy! :) $\endgroup$
    – Pratik Deoghare
    Commented Jan 10, 2011 at 13:26
  • $\begingroup$ $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. $\endgroup$
    – Peter Taylor
    Commented Jan 10, 2011 at 13:50
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Commented Jan 10, 2011 at 15:16
  • 3
    $\begingroup$ 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. $\endgroup$
    – Peter Taylor
    Commented Jan 11, 2011 at 18:31
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This answer should have much more upvotes $\endgroup$
    – Labo
    Commented Apr 7, 2020 at 18:32
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Labo
    Commented Apr 7, 2020 at 18:55
1
$\begingroup$

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! :)

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Mathieu Chapelle
    Commented Jan 10, 2011 at 13:05
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – Pratik Deoghare
    Commented Jan 10, 2011 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.