Let $G = (V, E)$ be a sparse oriented graph with $n$ vertices (i.e. no loops, no multi-edges, about 1-5% of all possible $n\cdot(n-1)/2$ edges are present). The value of $n$ is about $100$.
Let $A$ be the adjacency matrix of $G$ written for some specific default order of elements in $V$. I want to find out if there is a way to reorder the vertices in such a way that the adjacency matrix will display some regular structure.
To put it more formally, for any permutation $\sigma$ of $V$ let $A_\sigma$ denote the corresponding adjacency matrix of $G$ (which is the result of applying $\sigma$ to both rows and columns of $A$). Let’s further call a square matrix nice if it is a block matrix with square blocks of only two types:
- zero sub-matrices,
- band sub-matrices with bandwidth equal to 2 (i.e. all elements outside the main diagonal and the superdiagonal are zeros).
Is there an efficient way to find out whether $A_\sigma$ is nice for some $\sigma$? (Obviously, just looping through all the possible $n!$ permutations is not what I’m looking for given the magnitude of $n$.)
I'll appreciate any hints as well as suggestions to improve the definition of a nice matrix if this will simplify the answer itself.