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

• MHB
• evinda
In summary, the conversation discusses the creation of an algorithm for finding an optimal vertex cover of a tree in linear time, and clarifies the time complexity for DFS. The proposed algorithm involves visiting the root of the tree and its children recursively, and making sure that each edge is covered by at least one vertex. However, the time complexity is not accurately determined and further modifications need to be made to achieve the desired linear time complexity of $O(|V| + |E|)$.
evinda
Gold Member
MHB
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:

Code:
   DFS(node x){
discovered[x]=1;
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)

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!

## What is time complexity?

Time complexity is a measure of how much time a computer algorithm takes to solve a problem, based on the size of the input. It is usually measured in terms of the number of operations or steps the algorithm performs.

## Why is time complexity important?

Time complexity is important because it helps us understand the efficiency of an algorithm. By knowing the time complexity, we can predict how long an algorithm will take to run for different input sizes, and choose the most efficient algorithm for a given problem.

## What is Big O notation and how is it related to time complexity?

Big O notation is a mathematical notation used to describe the time complexity of an algorithm. It represents the upper bound or worst-case scenario for the number of operations an algorithm will perform. Time complexity is often expressed in terms of Big O notation.

## How do you analyze the time complexity of an algorithm?

To analyze the time complexity of an algorithm, you can count the number of operations or steps it performs for a given input size. You can also use mathematical analysis or run the algorithm with different input sizes and measure the time it takes to complete.

## What are some common time complexities and their corresponding Big O notations?

Some common time complexities and their Big O notations are:
- Constant time: O(1)
- Linear time: O(n)
- Logarithmic time: O(log n)
- Exponential time: O(2^n)
- Factorial time: O(n!)

• Programming and Computer Science
Replies
1
Views
1K
• Programming and Computer Science
Replies
1
Views
1K
• Programming and Computer Science
Replies
1
Views
1K
• Programming and Computer Science
Replies
1
Views
1K
• Programming and Computer Science
Replies
11
Views
3K
• Set Theory, Logic, Probability, Statistics
Replies
22
Views
1K
• Programming and Computer Science
Replies
2
Views
1K
• Programming and Computer Science
Replies
1
Views
1K
• Programming and Computer Science
Replies
22
Views
4K
• Programming and Computer Science
Replies
4
Views
2K