
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
May 9th, 2015, 03:47 AM  #1 
Member Joined: Nov 2013 Posts: 62 Thanks: 0  Complexity problem regarding Graph Isomorphism.
$A,B$ are symmetric matrices of graphs $G,H$ respectively. For $x \in G$, consider the graph $(Gx)$, it has vertices adjacent to $x$ and vertices nonadjacent to $x$. $ A_x$ is the symmetric matrix of the graph $(Gx)$, where $C$ is the symmetric matrix of the graph created by vertices of $(Gx)$ which are adjacent to $x$ and $D$ is the symmetric matrix of graph the created by vertices of $(Gx)$ which are not adjacent to $x$. $ A_x = \left( \begin{array}{cc} C & E \\ E^{T} & D\\ \end{array} \right) $ It should be noted, that 1. Interchanging/swapping any two rows(or columns) of $C$ does not affect matrix $D$ (and vice versa). 2. Any change in $C$ or $D$ or both $C$ and $D$ changes matrix $E$. If $G \simeq H $ then there exists $u \in H$ so that, $(Gx)\simeq (Hu)$, the matrix of $(Hu)$ is $B_u$, where $ B_u= \left( \begin{array}{cc} S & R \\ R^{T} & Q\\ \end{array} \right)$ Consider the situation where $S \neq C,D \neq Q$. Since $(Gx)\simeq (Hu)$ , there exists a permutation matrix $P$, so that $PQ=D$. Once $Q$ is arranged exactly like $D$ then $C$ can be arranged in linear/ polynomial time using the arrangement of rows of $E$ because after $Q=D$, the rows of $E$ and $R$ would be the same but arranged in different order. So, arrange the order of rows of $R$ like $Q$, it will make $S = C$. One of the $S,Q$ has vertices $<\frac{n}{2}$ where $ n=(Gx)=(Hu)$, consider the smallest matrix to find the permutation matrix $P$. So, to determine whether $(Gx)\simeq (Hu)$ is true or not, there are $n$ vertices to check. Let the time complexity to find this permutation matrix $P$ be $K(n/2)$. So, the complexity would be: $n*K(n/2)$ (omitting the time complexity of rearranging $E$ as it has less growth than $K$) But recursion of above method can be used to minimize the complexity of $K(n/2)$ for smallest matrix, say, $Q$, in that case, complexity would be $n*n/2* K(n/4)$ Using recursion, this gives a bound $\frac{n^{log_2(n)}}{2^{\sum log_2(n)}}$. Is this bound correct?? If not, what is the correct complexity of the above algorithm? Last edited by skipjack; May 9th, 2015 at 07:48 AM. 

Tags 
complexity, graph, isomorphism, problem, regrading 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Graph(regular) Isomorphism in n^(O(log2(n))) .  jim198810  Computer Science  8  May 9th, 2015 03:54 AM 
Graph Isomorphism Testing  mt2  Applied Math  0  October 18th, 2013 05:52 AM 
Complexity of Problem  UnOriginal  Applied Math  2  August 26th, 2009 07:05 AM 
complexity problem  baxy7  Applied Math  14  April 20th, 2009 02:29 PM 
isomorphism problem  Ujjwal  Linear Algebra  1  November 8th, 2008 05:48 PM 