2
$\begingroup$

Given a graph $G=(V,E)$ with $|V|=n,|E|=m$. I am reading a $\textit{brute force}$ solution to determining whether each candidate vertex cover of size $k \leq n$ is a vertex cover. The graph does not have loops.

As per page 2 of the notes here we have:

  • 1) $C(n,k) = O(n^k)$ $k$-subsets of $V$
  • 2) $O(kn)$ time to check whether a subset is a vertex cover

I am considering 2).

What I would think of would be to take each edge in our graph, for which there is a maximum of ${n \choose 2} = O(n^2)$, and check the candidate subset to see if at least one of the vertices is an endpoint of the edge, which would take $O(kn^2)$ checks.

I am not sure how the author arrived at $O(kn)$ operations, any insights appreciated.

$\endgroup$
2
$\begingroup$

The answer depends on the exact computation model and on the representation of the input. But here is one way to check whether a given subset is a vertex cover, assuming the graph is represented using adjacency lists.

Let the purported vertex cover be $S$, of size $k$. Start by counting all edges in $G$, stopping once you reach $kn$. If there are more than $kn$ edges, then $S$ is not a vertex cover, and we can stop. In time $O(|E|) = O(kn)$, you can count (1) $\sum_{i \in S} \deg(i)$ and (2) the number of edges connecting vertices in $S$. The total number of edges covered by $S$ is the difference between these two numbers, which you can compare to $|E|$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is brilliant thank you so much! $\endgroup$ – IntegrateThis Oct 30 '19 at 15:41
  • $\begingroup$ Sorry for the followup after accepting, but I had a bit more time this week to think about this problem, and I am still confused on one point. How do you compute the number of edges connecting vertices in $S$ in time $O(kn)$? $\endgroup$ – IntegrateThis Nov 2 '19 at 4:37
  • $\begingroup$ The answer is highly dependent on your model of computation. In some models you could just go over all edges and check whether both endpoints are in $S$. $\endgroup$ – Yuval Filmus Nov 2 '19 at 6:18
  • 1
    $\begingroup$ Truth be told, since this is an exponential time algorithm, we don’t really care about the time to check each potential solution. They just wrote something, without thinking too much. $\endgroup$ – Yuval Filmus Nov 2 '19 at 6:19

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.