# Algorithm for getting symetric vertex sets of undirected graph

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.

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.