3
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

You do not need to create any new graph.

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.