Checking if a $k$-subset of a graph is a vertex cover in time $O(kn)$

Question

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.

Answer 1

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|$.