Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Complexity Analysis problem of an Algorithm.

  1. May 9, 2015 #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: May 9, 2015
  2. jcsd
  3. May 9, 2015 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  4. May 9, 2015 #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

    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: May 9, 2015
  5. May 9, 2015 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    It would not, as it would make the subproblems C<->S and D<->Q completely independent. Or at least split them into groups.
    Sure, but checking that is not much progress on its own.

    You don't know whether x and u fit together or not.
     
  6. May 9, 2015 #5
    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.
     
  7. May 9, 2015 #6
    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.
     
  8. May 9, 2015 #7

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  9. May 9, 2015 #8
    :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.
     
  10. May 9, 2015 #9

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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".
     
  11. May 10, 2015 #10
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Complexity Analysis problem of an Algorithm.
Loading...