0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, 2017 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, 2017 at 16:09

Your Answer

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

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