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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.