1
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Juho
    Aug 27, 2021 at 7:09
  • $\begingroup$ You can ask for exactly $k$ for both problems, and they are pretty similar. $\endgroup$
    – Pål GD
    Aug 27, 2021 at 14:59

1 Answer 1

4
$\begingroup$

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.

Practical applications of independent set include the situation where a bunch of tasks each depend on some resources. You want to perform as many tasks as you can, but cannot perform two tasks which share the same resource. We model this problem by building a graph where each vertex is a task, and two vertices share and edge if they depend on the same resource. A feasible set of tasks is an independent set: a set of tasks such that no two tasks of the set are adjacent in the graph. Performing a single task is trivially a solution, but if we want to maximize the number of simultaneous tasks that we can perform, we need to look for a maximum independent set. Concretely, the tasks could for instance be courses in a university, and the resources the teachers and students: two courses cannot be held simultaneously if one student is taking both courses, or if the same teacher teaches the two courses.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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