Reorder adjacency matrices of regular graphs so they are the same

Question

Given a matrix A of a strongly $k$ regular graph G(srg($n,k,\lambda,\mu$);$\lambda ,\mu >0;k>3$). 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 not adjacent to $x$ and $D$ is the symmetric matrix of the graph created by vertices of $(G-x)$ which are adjacent to $x$.

$$ A_x = \left(\begin{array}{cccccc|ccc|c} 0&1&0&0&1&0&1&0&0&0\\ 1&0&1&0&0&0&0&1&0&0\\ 0&1&0&1&0&0&0&0&1&0\\ 0&0&1&0&0&1&1&0&0&0\\ 1&0&0&0&0&1&0&0&1&0\\ 0&0&0&1&1&0&0&1&0&0\\ \hline 1&0&0&1&0&0&0&0&0&1\\ 0&1&0&0&0&1&0&0&0&1\\ 0&0&1&0&1&0&0&0&0&1\\ \hline 0&0&0&0&0&0&1&1&1&0\\ \end{array}\right) = \left( \begin{array}{ccc} C & E & 0 \\ E^{T} & D & 1\\ 0 & 1 & 0\\ \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 the adjacency matrix of a regular graph and bigger than $D$.
2. There exists an algorithm that always order $D$ (for a vertex $x \in G$) takes $O(K)$ time (assumed to be polynomial/exponential, does not matter).

3. Each row of E has different permutation, i.e., rows might have same number of 1's but different permutation/arrangement of 1.

   For $n$ vertices there will be total $n$ numbers of $C,D$, each of them will take $O(K)$ (assumed to be polynomial) time to sort. If each $C$ takes time $O(f(n))$ to sort, then the total complexity will be $O(n \cdot K \cdot f(n))$.

Question: According to the three assumptions above, does there exist a polynomial time algorithm to sort $C$ so that $B=A$? I.e., is there a polynomial $f$ ?

The problem is connected to this question.

If anything is unclear, please ask a specific question, I will try my best to answer.

Answer 1

this will not be a direct answer at what does not really seem a direct question, which in its apparently big scope/ ambition pushes outside the bounds of SE questions but is nevertheless aimed to be a scientific and guiding response. you seem to be studying graph isomorphism in general, and as you are apparently aware the precise complexity of this is a major open problem. and it is known/ utilized generally that regular graphs are the "hard" ones for GI otherwise one can leverage nonuniform vertex degrees to (usually) significantly decrease the search space of vertex permutations.

so the best route to studying known hard scientific problems is to relate your own approach to the literature aka "terra cognita", which is quite large on this subject. for problems this significant, most straightforward approaches are attempted/ analyzed "somewhere". Here are some fairly close references to your technique, they share many close similarities. & then the task is to try to determine how your technique is different. Your basic idea of assigning columns/ rows of the adjacency matrix to different matrices is basically a partitioning algorithm of vertices into different sets. so:

• complexity of open partitions / open question by McKay on mathoverflow. he asks about the complexity of partitioning regular graphs into vertex partitions with the "equitability" property that may be similar to yours. he is the writer of nauty the top software for graph isomorphism computations.

• Efficient graph automorphism by vertex partitioning / Fowler et al. from abstract, an algorithm that runs in P time for all graphs tested including regular graphs.

My suggestion is also to try to convert your problem to isomorphism instances and empirically test nauty on it (just as the 1st paper uses empirical testing, which is accepted with conditions in this area), and that may be one of the more efficient known approaches, because nauty encodes vast swathes of state-of-the-art knowledge/ algorithm(s) on graph isomorphism complexity study.

Answer 2

Proposed Solution:

Arrangement of $G$: $A$ is the matrix of graph $G$ where $|G|=|A|=n$. Based on the adjacency of last vertex($n$ th vertex), A can be divided in to 4 sub-matrices where 2 are symmetric matrices($C,D$) and 2 are non square matrices($E^{T}, E$). One symmetric matrix, say, $D$ , has size $<n/2$. Repeat the whole procedure for matrix $D$ and $k$ th vertex $; 0<k<n$. This procedure can be done maximum $log_2(n)$ times.

Description of the Algorithm:$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 the graph 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 non-exponential 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. For example, 1st row may be placed in 4th row, but 1st row will look same in 4th row, here only order is changed(1st to 4th).

[ Once Q is arranged exactly like D, you can not change / reorder/ permute vertices which made Q, because if you change / reorder / permute vertices of Q, then Q will not be equal to D.If you can not change Q(=D), then there will be no column change in R(which is expected equal to E) as changing any column in R will change Q( but not S). So , after, Q is arranged exactly like D, change can be done in S matrix, if you change S, then only rows of E will change their order].

So, arrange the order of rows of $R$ like $E$, it will make $S = C$.