I am trying to understand computational complexity in the context of algorithms applied to graphs. In particular, I am wondering about the complexity of the following algorithm.
Let $G=(V,E)$ be a connected simple finite undirected graph.
1.) Label the vertices of $G$ with labels from $1$ to $|V|$ where each label appears exactly once.
2.) Calculate the $k$-fold cartesian product $G_k =(V^k, E_k)$ of $G$ with itself for a positive integer $k<|V|$.
3.) Remove all vertices $\bar{v}\in V^k$ which contain the label $1$ as well as the corresponding edges.
For a graph with $n$ vertices, the first step takes exactly $n$ operations. The third step takes $O( n^k)$ operations since we have to look at every vertex of $V^k$ exactly once and delete it or keep it. But I am not sure about the second step. Intuitively the whole algorithm should run in polynomial time but I am not sure and I am completely unexperienced in this area.
Thanks for any help :-)