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

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.

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

• This is brilliant thank you so much! – IntegrateThis Oct 30 '19 at 15:41
• 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)$? – IntegrateThis Nov 2 '19 at 4:37
• 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$. – Yuval Filmus Nov 2 '19 at 6:18
• 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. – Yuval Filmus Nov 2 '19 at 6:19