Graph Isomorphism Problem - Program Checking

Program Checking

Blum and Kannan have shown a program checker for graph isomorphism. Suppose P is a claimed polynomial-time procedure that checks if two graphs are isomorphic, but it is not trusted. To check if G and H are isomorphic:

• Ask P whether G and H are isomorphic.
  • If the answer is "yes':
    • Attempt to construct an isomorphism using P as subroutine. Mark a vertex u in G and v in H, and modify the graphs to make them distinctive (with a small local change). Ask P if the modified graphs are isomorphic. If no, change v to a different vertex. Continue searching.
    • Either the isomorphism will be found (and can be verified), or P will contradict itself.
  • If the answer is "no":
    • Perform the following 100 times. Choose randomly G or H, and randomly permute its vertices. Ask P if the graph is isomorphic to G and H. (As in AM protocol for graph nonisomorphism).
    • If any of the tests are failed, judge P as invalid program. Otherwise, answer "no".

This procedure is polynomial-time and gives the correct answer if P is a correct program for graph isomorphism. If P is not a correct program, but answers correctly on G and H, the checker will either give the correct answer, or detect invalid behaviour of P. If P is not a correct program, and answers incorrectly on G and H, the checker will detect invalid behaviour of P with high probability, or answer wrong with probability 2-100.

Notably, P is used only as a blackbox.