MHB What is the Time Complexity of this Vertex Cover Algorithm?

[evinda]

Hello! (Wave)

I want to write an algorithm that finds an optimal vertex cover of a tree in linear time $O(n)$, where $n$ is the number of the vertices of the tree..

A vertex cover of a graph $G=(V,E)$ is a subset $W$ of $V$ such that for every edge $(a,b)$ in $E$, a is in $W$ or $b$ is in $W$.In a vertex cover we need to have at least one vertex for each edge.
If we pick a non-leaf, it can cover more than one edge.
That's why I thought we can do it as follows:
We visit the root of the tree, then we visit one of its children, a child of the latter that we visited and so on..
Then if we have reached at a leaf, we check if we already have taken its father for the optimal vertex cover, and if not we pick it. Then, if the vertex that we picked for the optimal vertex cover has also other children, we pick the first of them and visit the leftmost children recursively and if we reach at the leaf and its father hasn't been chosen for the desired vertex cover, we choose it and so on.

I have written the following algorithm:

   DFS(node x){
      discovered[x]=1;
      for each (v in Adj(x)){
          if discovered[v]==0{
             DFS(v);
             if (v->taken==0){
                 x<-taken=1;
             }
          }
      }
    }

Its time complexity is $T(n)=\sum_{i=1}^{|V|} O(|V_i|+|E_i|) \leq \sum_{i=1}^{|V|} O(|E_i|) \leq \sum_{i=1}^{|V|} O(|E|)=O(|V| \cdot |E|)$.

($|V_i|, |E_i|$ are the number of vertices and edges respectively of the subtrees at the root of which we call DFS )

Is the time complexity I found right? Or have I calculated it wrong? (Thinking)

 

[lofgran]

Hello there!

Your proposed algorithm looks like a good start. However, there are a few things that need to be clarified in order to accurately determine the time complexity.

Firstly, it is important to note that the time complexity for DFS is typically represented as $O(|V| + |E|)$, where $|V|$ is the number of vertices and $|E|$ is the number of edges. This is because in the worst case scenario, we would have to visit all of the vertices and edges in the graph.

In your algorithm, you have defined $|V_i|$ and $|E_i|$ as the number of vertices and edges in the subtrees at the root of which you call DFS. However, it is not clear how these values are determined and how they relate to the overall time complexity.

Additionally, in your algorithm, you have a nested for loop where you are iterating through all of the adjacent vertices for each vertex. This would result in a time complexity of $O(|V| \cdot |E|)$, which is different from the linear time complexity that you are aiming for.

To achieve a linear time complexity, you would need to modify your algorithm so that it only visits each vertex and edge once. One approach could be to use a modified version of depth-first search (DFS) where you keep track of the vertices that have been visited and their adjacent vertices. This would allow you to only visit each vertex and edge once, resulting in a time complexity of $O(|V| + |E|)$.

I hope this helps clarify the time complexity for your algorithm. Let me know if you have any further questions or concerns. Keep up the good work!