Combinatorial algorithm

  • #1

Main Question or Discussion Point

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## ?**
 

Answers and Replies

  • #3
that discussion was incomplete and was the general case, this more specific. It would easier, if this thread is concluded.
 
  • #5
Consider ##G## as a strongly ##k## regular graph G(srg(##n,k,\lambda ,\mu##);##\lambda ,\mu >0##).
 

Related Threads on Combinatorial algorithm

  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
17
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
574
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
20
Views
738
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
19
Views
4K
Top