22
$\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?

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

$\endgroup$
  • $\begingroup$ Thank you, also for introducing me to Modular Decomposition! $\endgroup$ – gphilip Jan 11 '11 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)

$\endgroup$
  • 6
    $\begingroup$ The same idea on adjacency lists gives $O(m+n)$. $\endgroup$ – Radu GRIGore Jan 10 '11 at 14:08
  • $\begingroup$ Now I'm nuking a fly ;) $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 10 '11 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 Jan 11 '11 at 18:35
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.

$\endgroup$
  • $\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 Jan 10 '11 at 12:14
  • 1
    $\begingroup$ @TheMachineCharmer: Thank you :) Yes, if the graph is undirected. $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 10 '11 at 12:16
  • $\begingroup$ Yes. Exactly! :) $\endgroup$ – Pratik Deoghare Jan 10 '11 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.

$\endgroup$
  • $\begingroup$ I see no problem with $A^2$. Any examples? btw, system on this site is NOT crazy! :) $\endgroup$ – Pratik Deoghare Jan 10 '11 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 Jan 10 '11 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 Jan 10 '11 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 Jan 11 '11 at 18:31
3
$\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.

$\endgroup$
2
$\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.

$\endgroup$
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! :)

$\endgroup$
  • 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 Jan 10 '11 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 Jan 10 '11 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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