- #1
secondprime
- 47
- 0
Given a matrix A of a regular graph G. The matrix A can be divided into 4 sub matrices based on adjacency of vertex ##x \in G##.
## 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 the graph created by vertices of ##(G-x)## which are not adjacent to ##x##.
http://i.stack.imgur.com/qL2rD.jpg
## 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##.
**Problem:** If some vertices of ##G## is rearranged(i.e. permuted), ##A## will be different, say, this new matrix is ##B##. Again, matrix ##B## can be divided into 4 sub matrices based on adjacency of vertex ##x \in G## and ## B_x## can be obtained.Assume-
1. ##C## is always a regular graph’s matrix and bigger than ##D##.
2. There exists an algorithm that always order ##D##(for a vertex ##x \in G##) takes ##K## times(assumed to be polynomial).
3. Each row of E has different permutation, i.e. , rows might have same number of 1's but there is no two rows which can be permuted to each other. Say, ##r_x , r_y## are two rows, there is no permutation ##\sigma## so that, ## \sigma r_x=\sigma r_y##. *So, there is no way ##E## to be a zero matrix or matrix of all 1's or a matrix has some identical rows.* For ##n## vertices there will be total ##n## numbers of ##C,D##, each of them will take ##K##(assumed to be polynomial) time to sort. If Each ##C## takes ##f## time to sort, then the total complexity will be ##n\times K\times f##.
**according to above 3 assumptions, Does there exist a polynomial time algorithm to sort ##C## so that ##B=A##? i.e. Is there a polynomial##f## ?**
## 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 the graph created by vertices of ##(G-x)## which are not adjacent to ##x##.
http://i.stack.imgur.com/qL2rD.jpg
## 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##.
**Problem:** If some vertices of ##G## is rearranged(i.e. permuted), ##A## will be different, say, this new matrix is ##B##. Again, matrix ##B## can be divided into 4 sub matrices based on adjacency of vertex ##x \in G## and ## B_x## can be obtained.Assume-
1. ##C## is always a regular graph’s matrix and bigger than ##D##.
2. There exists an algorithm that always order ##D##(for a vertex ##x \in G##) takes ##K## times(assumed to be polynomial).
3. Each row of E has different permutation, i.e. , rows might have same number of 1's but there is no two rows which can be permuted to each other. Say, ##r_x , r_y## are two rows, there is no permutation ##\sigma## so that, ## \sigma r_x=\sigma r_y##. *So, there is no way ##E## to be a zero matrix or matrix of all 1's or a matrix has some identical rows.* For ##n## vertices there will be total ##n## numbers of ##C,D##, each of them will take ##K##(assumed to be polynomial) time to sort. If Each ##C## takes ##f## time to sort, then the total complexity will be ##n\times K\times f##.
**according to above 3 assumptions, Does there exist a polynomial time algorithm to sort ##C## so that ##B=A##? i.e. Is there a polynomial##f## ?**