Complexity Analysis problem of an Algorithm.

  • #1
##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?
 
Last edited by a moderator:

Answers and Replies

  • #2
35,499
11,947
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.
 
  • #3
"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.
 
Last edited:
  • #4
35,499
11,947
"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.
 
  • #5
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.
 
  • #6
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.
 
  • #7
35,499
11,947
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.
 
  • #8
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..

:smile: 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.
 
  • #9
35,499
11,947
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".
 

Related Threads on Complexity Analysis problem of an Algorithm.

Replies
1
Views
578
  • Last Post
Replies
1
Views
668
Replies
4
Views
8K
  • Last Post
Replies
1
Views
2K
Replies
1
Views
2K
Replies
1
Views
4K
Replies
2
Views
5K
Replies
1
Views
2K
Replies
3
Views
2K
Top