2
$\begingroup$

Given a graph $H$. A set of permutations $\alpha$ which contains permutations of vertices of $H$.

The permutation set $\alpha$ has automorphisms of subgraph $H_1, H_2,..... H_x$ where $x$ is the number of total subgraphs. These subgraphs are connected. These permutations can be extended to the automorphism of $H$. By extending, we mean that automorphism of subgraphs can be extended to the automorphism of graph $H$. This concept is similar to E. Luks' paper of graph siomorphism of bounded valence.

Each subgraph has constant number of vertices. The adjacency matrix of $H$ is -

$$H = \begin{bmatrix} H_{(x)} & R_{(x, x-1)} & R_{(x,x-2)} & \dots & \dots & R_{(x,1)} \\ R_{(x,x-1)^{T}} & H_{(x-1)} & R_{(x-1,x-2)} & \dots & \dots & R_{(x-1,1)} \\ \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\ R_{(x,1)^{T}} & R_{(x-1,1)^{T}} & R_{(x-2,1)^{T}} & \dots & \dots &H_{1} \end{bmatrix}$$

The adjacency matrix of graph $H_k \cup H_e$ is $M_{(k,e)}$ where $M_{(k,e)} =\left( \begin{array}{ccc} H_e & R_{k,e} \\ R_{k,e}^{T} & H_k\\ \end{array} \right) $, where, $R_{k,e}$ is the non symmetric sub-matrix of adjacency matrix $H$. Here, $R_{k,e}$ represents edges between $H_k, H_e$.

Problem: How to find an automorphism of $H$ in polynomial time (in $\alpha$)?

Note:

  1. $\alpha$ is the generating set of autmorphsim group of $H$.
$\endgroup$
  • $\begingroup$ $R_{k,e}$ is set of edges between subgraph $H_k$ and subgraph $H_{e}$ ? $\endgroup$ – Jim Jun 6 '16 at 4:11
  • $\begingroup$ I don't understand the problem statement. $\alpha$ is a set, right? What is each element? Is it a permutation of vertices of $H$? Is it an automorphism of some $H_i$? What does it mean "these permutations can be extended to the automorphism of $H$"? How does $H$ relate to $H_1,\dots,H_x$? Are they a disjoint partition of the vertices of $H$? Is this a directed graph or an undirected graph? What makes you think it's possible to build an automorphism of $H$ in polynomial time? I presume you want a non-trivial automorphism? What approaches have you tried? $\endgroup$ – D.W. Jun 6 '16 at 4:40
  • $\begingroup$ @D.W. , we can start with $H_1$ and $H_2$ and see direct products of $\alpha$ creates an automorphism of graph $H_1 \cap H_2$ . Since it is given, that permutations of $\alpha$ extend to an automorphism of $H$, so, I will find an automorphism, and recurse the process, until I find the auto of $H$ $\endgroup$ – Jim Jun 6 '16 at 4:47
  • $\begingroup$ 1. "I don't understand the problem statement. α is a set, right? What is each element? " Is it a permutation of vertices of H? Is it an automorphism of some Hi?- yes to all. 2. What does it mean "these permutations can be extended to the automorphism of H"? -- this is term you use when you find auto: from subgraphhs and extend it to whole graph 3. Are they a disjoint partition of the vertices of H? ----yes 4. Is this a directed graph or an undirected graph? --- unirected. @D.W. $\endgroup$ – Jim Jun 6 '16 at 4:51
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jun 6 '16 at 9:02
2
$\begingroup$

If you only want an automorphism, then just consider the identity permutation. That's an automorphism -- the trivial automorphism.

If you want a non-trivial automorphism, then if I understand your problem statement, this is as hard as the graph automorphism problem. No polynomial-time algorithm is known for this problem. It's not known to be NP-complete (it's not even known to be GI-complete). Nonetheless, finding a polynomial-time algorithm for this problem is an open problem, so you shouldn't expect it to be easy to find a polynomial-time algorithm for your problem, either.

In practice you can use open-source tools like Nauty, BLISS, or SAUCY to find an automorphism; on most graphs they (empirically) are very fast.


Justification of claim that this is as hard as graph automorphism:

We can reduce graph automorphism to your problem. Let $G$ be an arbitrary undirected graph, with $n$ vertices. Construct an undirected graph $H$ with $2n$ vertices as follows: for each vertex $v$ of $G$, add another vertex $v'$, and add an edge $(v,v')$. Keep all the edges between unprimed vertices, but don't add any edges between primed vertices.

Note that the automorphisms of $G$ are in one-to-one correspondence with the automorphisms of $H$. If $\pi$ is an automorphism of $G$, it can be extended to an automorphism of $H$ simply by permuting the primed vertices in the same way as the unprimed vertices. If $\pi'$ is an automorphism of $H$, by projecting it to the vertex set of $G$ we obtain an automorphism of $G$.

Now define $H_1,\dots,H_n$ as follows: each $H_i$ is the subgraph induced by the two vertices $v_i,v'_i$. In other words, $H_i$ has vertex set $\{v_i,v'_i\}$ and has a single edge $(v_i,v'_i)$. Thus, $H_i$ has a non-trivial automorphism that swaps $v_i$ and $v'_i$, and this corresponds to a permutation $\pi_i$ of $H$ (one that leaves all other vertices of $H$ fixed). Define $\alpha$ to be this set of permutations.

Now if you can find a non-trivial automorphism of $H$, you can immediately obtain a non-trivial automorphism of $G$ (i.e., you've found a way to solve the graph automorphism problem on an arbitrary graph $G$). If $H$ has no non-trivial automorphism, neither does $G$. This completes the reduction.

$\endgroup$

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.