1
$\begingroup$

Considering this factor $2$ minimum vertex cover approximation algorithm :

Repeat while there is an edge:

Arbitrarily pick an uncovered edge $e=(u,v)$ and add $u$ and $v$ to the solution. Delete $u$ and $v$ from the graph. Finally output the candidate cover.

I want to find the worst case running time of this algorithm. Since in a fully connected graph we have $O(n^2)$ edges, then the loop will run at most $O(n^2)$ times.

Here I am not sure what the maximal number of delete operations could be or perhaps for less than $O(n^2)$ edges being processed in the loop there would be some scenario with a large number of delete operations would contribute to the overall complexity.

I want to say naively that in the worst case you simply multiply the max number of edges possible with the max number of delete operations possible (both $O(n^2))$ giving $O(n^4)$, but this seems wrong.

Any insights appreciated.

$\endgroup$
1
$\begingroup$

It depends on which data structure you use to store the graph.

For example, suppose the nodes are represented as $0,\ldots,n-1$, and the edges are stored as a list of pairs of nodes. We can build an boolean array $\mathrm{arr}$ of length $n$ initialized with all $\texttt{true}$s, and when a node $i$ is deleted, we simply mark $\mathrm{arr}[i]$ as $\texttt{false}$. Each time we deal with an edge, we first check if any of its endpoints is deleted to see if the edge has already been covered. With such data structures, your algorithm runs in $O(n^2)$.

$\endgroup$
  • $\begingroup$ Makes sense, thanks. $\endgroup$ – IntegrateThis Nov 2 '19 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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