In the subgraph isomorphism problem we need to establish a certifier where we can map the edges from induced map to the original map. And it will take polynomial time to achieve.
Does this mean that the certifier always has a time complexity equal to some polynomial function of number the nodes in original map ? Thank you !
There exist certifiers that run in time worst than polynomial time, but to prove that subgraph isomorphism is in NP, you need to find one that runs in polynomial time.
Being polynomial in the size of the graphs is equivalent to being polynomial in the number of vertices (because the size of the graph is polynomial in the number of vertices). As the target graph is always bigger than the pattern graph, it is also equivalent to be polynomial in the size of the target graph.