0
$\begingroup$

In the Introduction to Algorithms Book By Thomas H. Cormen, Third Edition, they give an approximation algorithm for the Vertex Cover Problem with 2-approximation ratio:

enter image description here

Where G is undirected graph. The complexity of this algorithm is O(V+E). I do not know why. It should be O(E) since the while loop in line 3 clearly will loop |E| times (E is the set of edges in G). The cost of line 6 is at most 1?

$\endgroup$
1
  • 1
    $\begingroup$ I think this analysis implicitly assumes that you have to traverse every vertex to parse the edges, or that isolated vertices were scanned and deleted. But if appropriate data structures are used, I tend to agree with you that the algorithm is $O(|E|)$. For instance, if your graph has $1$ edge and $1$ million isolated vertices, you would only loop once. In any case, $O(|V| + |E|)$ is not wrong since $O$ gives an upper bound -- though $O(|E|)$ might be more accurate. $\endgroup$ Commented Sep 6, 2022 at 12:52

3 Answers 3

1
$\begingroup$

You can use a boolean array of length $|V|$ to check whether a vertex $u$ has already been seen or not. Assuming $V = \{0, 1, …, n-1\}$, the algorithm could be re-written as:

Input: graph G as an adjacency lists array

Initialize C as an empty set
for each edge e = {u, v} in E do
    if neither u nor v is marked then
       Add e to C
       mark u and v
return C

The complexity would indeed be $\mathcal{O}(|V| + |E|)$.

$\endgroup$
8
  • $\begingroup$ But why? In your algorithm the loop will iterate |E| times. So how it is V+E? $\endgroup$
    – Jarvis
    Commented Sep 3, 2022 at 17:34
  • 1
    $\begingroup$ The marking inside the loop is done using a boolean array of length $|V|$. Since the array needs to be initialized, that explains the $|V|$ part in the complexity. $\endgroup$
    – Nathaniel
    Commented Sep 3, 2022 at 19:02
  • 1
    $\begingroup$ Another thing is: depending on the structure of the input, you could not have access to the set of all edges. For example, if the graph is implemented as an adjacency lists array, you would have to check each adjacency list to create the set of all edges or iterate through all of them. Such an operation would be done in $\mathcal{O}(|V| + |E|)$. $\endgroup$
    – Nathaniel
    Commented Sep 3, 2022 at 19:07
  • $\begingroup$ Thanks @Nathaniel . I understand your first point: initialization would take $\mathcal{O}(|V|)$ and the loop would take $\mathcal{O}(|E|)$, so the overall complexity is $\mathcal{O}(|V|+|E|)$ because the bigger term might be any of these two. Right? $\endgroup$
    – Jarvis
    Commented Sep 3, 2022 at 20:32
  • $\begingroup$ As for your second point, I still do not understand why it is $\mathcal{O}(|V|+|E|)$ to iterate over all edges in $E$. The way I see is: the size of adjacency list array is $|V|$ (i.e., there are exactly $|V|$ lists), and the sum of all lists sizes is $|E|$. Hence, the loop will iterate over $|E|$ edges. So how it becomes $\mathcal{O}(|V|+|E|)$ ! $\endgroup$
    – Jarvis
    Commented Sep 3, 2022 at 20:36
0
$\begingroup$

I think the only thing missing in your analysis is the cost of adding the two vertices to the set $C$,which at the very least be $O(1)$ per vertex, if $C$ is implemented as a simple list. With that you will get the $O(V+E) $ bound.

$\endgroup$
0
$\begingroup$

You need to specify the data structure where you maintain E' to be able to argue about running time. CLRS specifies adjacency list. But it does not explain how to remove one of the end points of the chosen edge from all the other lists.

$\endgroup$

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.