 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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      