Suppose you are given two graphs with $v$ vertices and wish to check whether they are isomorphic are not. One possible way to do this is to enumerate all possible permutations of the $v$ vertices and see if any of these permutations create a bijection between the edges and vertices of the graphs. However, this type of algorithm takes a global view of the problem, I was wondering if there was an algorithm that took a more local view. That is, if you input a graph into this algorithm it will output a specific vertex (up to automorphism of course) regardless of how the vertices are labeled.
If we called the local view algorithm $P(G)$, then the full algorithm to check isomorphism between graphs $G$ and $H$ would work as follows:
$1)$ Run $P(G)$ and $P(H)$
$2)$ Store the vertices outputted as equivalent vertices
$3)$ Remove these vertices from $G$ and $H$. Return to step $1)$
After $v$ steps, you will have a list of $v$ pairs of equivalent vertices. You then check whether this list actually describes an isomorphism between the graphs. If it does, the graphs are isomorphic, if not then they are not.
Such an algorithm $P(G)$ is not computable in polynomial time as the other steps in the algorithm above can be computed in polynomial time. If this were not the case, then graph isomorphism would be computable in polynomial time (this is not currently known). Here is an example for a specific type of graph: Suppose $G$ and $H$ are graphs such that every vertex has a unique degree and every vertex is only connected to itself. Then $P(G)$ simply outputs the vertex with the largest degree.
Reiterating the question: Does such a local algorithm exist for all graphs?
Best Answer
The closest you can get to this is to use some sort of Canonical Labeling for your graph (which will put all the vertices into some specified ordering), and then the special vertex you return can be the first vertex according to this labeling. Of course this takes a more global view, because you would just see if $G$ and $H$ look the same under the canonical labeling.
There is no (known) way to do this with a more local view, as you suggest, because you really need to consider all of the vertices in order to decide which "special" vertex to return (if you want this special vertex to be invariant under the isomorphisms of the graph in some way). So of course it is just as complicated to decide a single vertex to choose as the "first" vertex as it will be to decide an ordering for all of the vertices.
For more information about canonical labelings, you can look at some information involved in the nauty package for testing graph isomorphisms.