The certificate is the vertex mapping function. If we have the mapping function. we can verify the isomorphic property easily.
July 13, 2007
Exercises 34.1-5
Because we can use polynomial time algorithm to enlarge the problem instance. Hence the polynomial time call may result exponential time algorithm.
Exercises 34.1-4
No, it is pseudo polynomial. Because W is not polynomial to the input size.
Exercises 34.1-1
Since the simple path’s length is at most |V|, we can do binary search on path length.
