Given any graph $G$ on $V(G)=\{1,\dots,n\}$ and its adjacency matrix $$A(G)=\left(\matrix{ A_{1,1} & A_{1,2} & \dots & A_{1,n}\\ A_{2,1} & A_{2,2} & \dots & A_{2,n}\\ &&\dots&\\ A_{n,1} & A_{n,2} & \dots & A_{n,n} }\right)$$ any permutation on $\{1,\dots,n\}$ defines a new isomorphic graph $G'$. A common approach to canonization is to take the lexicographically minimal string $A'_{1,2}A'_{1,3}\dots A'_{n-1,n}$ (i.e. the upper/lower triangular matrix) such that $G$ is isomorphic to $G'$ with $A'=A(G')$.

If you now consider a permutation on $I=\{(i,j)\mid 1\leq i<j\leq n\}$ or equivalently a bijective function $\pi : \{1,\dots,{n \choose 2}\} \rightarrow I$, we can try to minimize $A'_{\pi(1)},\dots,A'_{\pi({n\choose 2})}$ instead, or at least to compute the first $k$ bits of the minimal string.

Observe that the complexity of this task heavily depends on the choice of $\pi$:

  1. If you stick with default permutation (upper triangular matrix) you can easily compute the first $2n-1$ bits in polynomial time (adjacent vertices with maximal degrees).
  2. If you choose $\pi(i)=(i,i+1)$ for the first $\sqrt[c]{n}$ positions, you can reduce HamiltonPath to this in polynomial time.

Now my questions:

  1. Given a fixed function $k$ and input $(G,\pi)$ how hard is it to compute the first bits $k(|V(G)|)$ of the minimal string $A'_{\pi(1)},\dots,A'_{\pi({n\choose 2})}$? Is there any (not necessarily strictly) monotonically increasing $k$ for which this is feasible?
  2. Is there a $\pi$ s.t. even $\omega(n)$ bits can be computed in polynomial time?
  3. Do you know any other reductions to a problem of this kind where $\pi$ is "fixed" (i.e. only depends on $|V(G)|$) and the input has the form $(G,k)$ or $G$ (i.e. $k$ is "fixed" too)?

Note: Answering (1) is enough to get accepted.

Edit: In the meanwhile there appeared a somewhat connected question: Is induced subgraph isomorphism easy on an infinite subclass?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.