Complexity Analysis problem of an Algorithm.

[secondprime]

$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)$ ,so, 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 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$ is $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 complexity of above algorithm?

 

[mfb]

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 same but arranged in different order. So, arrange the order of rows of $R$ like $Q$, it will make $S = C$.

In the worst case, all columns of E and R are the same or at least form a few large groups, then you reduced your problem size by 1/2, but you have to check n nodes to do so.

 

[secondprime]

"In the worst case, all columns of E and R are the same"
or rows??
correct. but-
in that case you don't not need to divide $D,Q$ divide $C,S$ again, if you find the proper arrangement of $C,S$it would provide proper $D,Q$ as earlier

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 same but arranged in different order. So, arrange the order of rows of $R$ like $Q$, it will make $S = C$

it can be checked in poly/linear time that whether E, R has all row same or not.

"but you have to check n nodes to do so."
not understood why you said that, adjacent and non adjacent are in 2 different group, you would not seek a vertex (which is in a group of adjacent to u/x, i.e in C) in a gorup of non adjacent to x/u, i.e in D.

 

[mfb]

"In the worst case, all columns of E and R are the same"
or rows??
correct. but-
in that case you don't not need to divide $D,Q$ divide $C,S$ again, if you find the proper arrangement of $C,S$it would provide proper $D,Q$ as earlier

It would not, as it would make the subproblems C<->S and D<->Q completely independent. Or at least split them into groups.

it can be checked in poly/linear time that whether E, R has all row same or not.

Sure, but checking that is not much progress on its own.

"but you have to check n nodes to do so."
not understood why you said that, adjacent and non adjacent are in 2 different group, you would not seek a vertex (which is in a group of adjacent to u/x, i.e in C) in a gorup of non adjacent to x/u, i.e in D.

You don't know whether x and u fit together or not.

 

[secondprime]

You don't know whether x and u fit together or not.

yes, I don't know, so I am going to check all possible combination. If you follow a brute force search, then you would have to try all n vertices. But as there is no need to look for a vertex of D in C, the search is cut down to<= n/2

"Sure, but checking that is not much progress on its own."

I meant that this checking would spare the the checking of Q, instead of that , start S again.

 

[secondprime]

as it would make the subproblems C<->S and D<->Q completely independent.

you are right again sir, but E, R depends on C,S,D,Q and vice versa, once you figure out S like C, you will get D=Q with the help of E,R as written for Q,D and C,S in the first post.

 

[mfb]

yes, I don't know, so I am going to check all possible combination. If you follow a brute force search, then you would have to try all n vertices. But as there is no need to look for a vertex of D in C, the search is cut down to<= n/2

The search is cut down to <n/2 for one subproblem.

So what you are doing:
1) Pick x, pick some u with the same number of edges as x. If they don't match you'll find out later, then you have to pick a different u, up to n times.
2) make C,D,S,Q, without loss of generality let's assume D is smaller than C
3) identify nodes in D and Q with each other, this is the general problem but reduced to < n/2.
4) sort E and R, make groups of nodes that are indistinguishable based on E and R.
5) identify groups in C and S with each other, this is the general problem but reduced to <= n-2.

Both steps 3 and 5 lead to recursion, in the worst case n-2 vertices are left in step 5: this happens if you pick x and u to have one edge (or n-2 edges), and if the single vertex connected to it (or the single vertex not connected to it) is either connected to no other vertex or to all other n-2 vertices.

If step 1 fails, pick the next u. If there is no u left, go one step up in the recursion depth.

Doing something up to n times to reduce the number of vertices by 2 gives a horrible complexity.

 

[secondprime]

The search is cut down to <n/2 for one subproblem.

in the worst case n-2 vertices are left in step 5: this happens if you pick x and u to have one edge (or n-2 edges), and if the single vertex connected to it (or the single vertex not connected to it) is either connected to no other vertex or to all other n-2 vertices..

Sir, in this case, that particular vertex is distinguishable and don't need the described algorithm!


You have been patient with me, I appreciate that. I am going to ask you a favor, it would be a great help.

just consider the below case- Assume that, at every step, all rows and columns of E would be distinguishable , in that case, would you agree with the given upper bound?? If not, please write down the reasons.

 

[mfb]

An upper bound for a special case is pointless. It might be true, but that is the same as saying "this sorting algorithm is linear as upper bound if we start with a sorted list".

 

[secondprime]

I made a presentation according to the algorithm I described, click the below link,
https://www.academia.edu/11354697/Graph_regular_Isomorphism_in_n_O_log2_n_
Ignore the complexity analysis( which is bigger than the above post).