2
$\begingroup$

For my application problem, I am searching for an algorithm that can find all symmetric vertex sets of an undirected labeled graph.

My definition of symmetric vertex set is: Let $G$ be a graph with vertex set $V$ and edge set $E = \{u,v\}, u,v \in V$. If $S \subseteq V$ and there exits an isomorphism $f$ on this graph such that for every $v\in S$, we have $f(v) \in S$, then $S$ is called a symmetric vertex set.

I have searched some graph matching algorithms, but have gotten no clue so far. I am wondering if any one can give me a hint, I will work on it.

$\endgroup$
0
5
$\begingroup$

You want to know the orbits of the action of the automorphism group of a graph on its vertices. This is equivalent to graph isomorphism, for which no really simple algorithms are known. Practical graph isomorphism algorithms, which work fast in practice, are known – check nauty for example. Apparently nauty can compute the automorphism group directly, from which you can easily compute the orbits of its action on the vertices.

Solving GI using your task. Given connected graphs $G_1,G_2$, we want to know whether they are isomorphic. Compute the orbits, and check whether any of them mixes vertices from $G_1$ and $G_2$.

Solving your task using GI. Given a graph $G$ and two vertices $x,y$, create two copies of $G$ and attach a long path to $x$ in one of them and to $y$ in the other. The two vertices belong to the same orbit if these graphs are isomorphic.

The second reduction involves $n^2$ invocations of GI, whereas $\log B_n \approx n\log n$ (here $B_n$, the $n$th Bell number, is the number of partitions of $\{1,\ldots,n\}$). This means that any reduction needs $\Omega(n\log n)$ invocations of GI, and suggests that my reduction can be improved.

$\endgroup$
1
  • $\begingroup$ Hello Yuval, thank you so much. I see that what I am looking for is "orbit"! I will do more research on this concept and nauty! $\endgroup$ – Pepper M Feb 11 '17 at 17:53

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.