# Why is Independent Set "at least" and Vertex Cover "at most" k

The decision version of the Independent Set and Vertex Cover problems are phrased as:

Given a graph G and a number k, does G contain an independent set of size at least k?

Given a graph G and a number k, does G contain a vertex cover of size at most k?

My question is, what is the reasoning behind using "at least" for the independent set and "at most" for the vertex cover? When we want to optimize, we want to maximize Independent Set and minimize Vertex Cover. So shouldn't it be finding at most size k for Independent Set and at least size k for Vertex Cover?

• That would be rather trivial, e.g., I could just output say an independent set of size 1 and that would be of size at most k. So no matter what you ask for with your choice of k (> 0), I can always give out that single node and be done with it.
– Juho
Aug 27, 2021 at 7:09
• You can ask for exactly $k$ for both problems, and they are pretty similar. Aug 27, 2021 at 14:59

## Theory

Note that the set of all vertices is trivially a vertex cover, and any set containing only one vertex is trivially an independent set.

What is hard with an independent set is to make it larger. The more vertices it has, the more it "risks not being independent" by two vertices being adjacent. Formally, if U and V are two sets of vertices such that $$U \subseteq V$$, then "V is independent" implies "U is independent" (or equivalently: "U is not independent" implies "V is not independent").

What is hard with a vertex cover is to make it smaller. The more vertices you remove, the more chances there are that you no longer have a vertex cover. Formally, if U and V are two sets of vertices such that $$U \subseteq V$$, then "U is a vertex cover" implies "V is a vertex cover" (or equivalently, "V is not a vertex cover" implies "U is not a vertex cover").

## Applications

Practical applications of vertex cover include the situation where you want some service to be available to everyone, while minimizing the cost of deploying your service everywhere. For instance, imagine we need to build fire stations in a city. I have divided the city into small districts, and I want to make sure that every district either has its own fire station, or is adjacent to a district with a fire station. What I need to find, then, is a vertex cover of the graph formed by the districts. Of course, I could just put one fire station in every district, which would trivially solve the problem; but if I want to minimize my budget, then I need to find a minimum vertex cover.