My Math Forum Complexity problem regarding Graph Isomorphism.
 User Name Remember Me? Password

 Computer Science Computer Science Forum

 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 $(G-x)$, it has vertices adjacent to $x$ and vertices non-adjacent to $x$. $A_x$ is the symmetric matrix of the graph $(G-x)$, where $C$ is the symmetric matrix of the graph created by vertices of $(G-x)$ which are adjacent to $x$ and $D$ is the symmetric matrix of graph the created by vertices of $(G-x)$ 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, $(G-x)\simeq (H-u)$, the matrix of $(H-u)$ 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 $(G-x)\simeq (H-u)$ , 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=|(G-x)|=|(H-u)|$, consider the smallest matrix to find the permutation matrix $P$. So, to determine whether $(G-x)\simeq (H-u)$ 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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post jim198810 Computer Science 8 May 9th, 2015 03:54 AM mt2 Applied Math 0 October 18th, 2013 05:52 AM UnOriginal Applied Math 2 August 26th, 2009 07:05 AM baxy7 Applied Math 14 April 20th, 2009 02:29 PM Ujjwal Linear Algebra 1 November 8th, 2008 05:48 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top