For $f : V → V$ which is authomorphism of directed graph $G = (V, E)$, $$\#f = |\{v : f(v) \neq v\}|$$ For graph $G$ we denote: $$\#G = \max\{\#f : \text{$f$ is isomorphism $G$} \}$$

Prove that if $P = NP$ then function $G\to\#G$ is polynomially computable.

My problem is that I can't think about isomorphisms. I know that thanks to assumption in polynomial time I can check if two graphs are isomorphic. The problem is however that I can't generate candidate for checking it.


Consider the decision version of computing $\#G$:

$L=\{(G,k) | \text{$G$ has an automorphism $f$ with $\#f\ge k$}\}$

$L$ is obviously in NP (an automorphism $f$ with $\#f\ge k$ is a witness). If $\mathsf{P=NP}$ then $L\in P$, and you can compute $\#G$ in polynomial time using binary search.

  • $\begingroup$ can it be $L=\{(G,k) | \text{$G$ has an automorphism $f$ with $\#f = k$}\}$ in place of your $L=\{(G,k) | \text{$G$ has an automorphism $f$ with $\#f\ge k$}\}$. And binary search is also not needed $\endgroup$ – Haskell Fun Aug 14 '17 at 13:14
  • $\begingroup$ You can define $L$ that way, but you will still need to search for the maximum in order to compute $\#G$ (one oracle call to $L$ is not enough). $\endgroup$ – Ariel Aug 14 '17 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.