# A question about the work per recursive call in FPT vertex cover of size k algorithm

I have been looking at the FPT(Fixed Parameter) algorithm for checking if a vertex cover of size k exists.The algorithm goes as follows:

VertexCoverFPT$$(G, k)$$

if $$G$$ has no edges then return true

if $$k=0$$ then return false

let $$uw$$ be some edge of $$G$$

if VertexCoverFPT$$(G-u, k-1)$$ then return true

if VertexCoverFPT$$(G-w, k-1)$$ then return true

return false

Its said that this algorithm has $$2^k$$ recursive calls each with $$O(n)$$ of work in each recursive call. My question is how is it that there is only $$O(n)$$ work in each recursive call when we need to create the 2 graphs $${G-u}$$ and $${G-v}$$ (u and v are the vertices we are currently checking) which takes $$O(V+E)$$ time (Doing a deep copy of graph G excluding the node and the edges connected to it). Is there a more efficient way than constructing $${G-u}$$, $${G-v}$$ from G or am I missing something?

You can simply maintain an additional array $$VT$$ of size $$|V| = n$$ such that $$VT[i] = 1$$ if the vertex $$i$$ is deleted from the graph. Otherwise, $$VT[i] = 0$$.
While accessing an edge $$(i,j)$$, first the algorithm can check if $$VT[i]$$ and $$VT[j]$$ are both $$0$$ or not. If both are $$0$$ then the algorithm access that edge. Otherwise, it does not.
In addition to it, maintain the count of edges a vertex $$i$$ is currently connected to. Suppose the count is stored in an array $$C$$ of size $$n$$. In the beginning of the algorithm $$C[i]$$ is initialized to the $$degree(i)$$.
Accessing an Undeleted Edge: Go to the adjacency list of that vertex which has $$VT[i] = 0$$ and $$C[i] \neq 0$$. Since we know that at least one edge in the list is not deleted, the algorithm will find an undelete edge in $$O(n)$$ time. Updating the count array after deleting a vertex takes $$O(n)$$ time. Overall operation is $$O(n)$$ time.