Exercise 2, Question 2

dcs92 13 Nov 2018 11:59

Hi,

I'm a little bit confused by question 2. You said given a graph and a number k you want us to find a set of size k that satisfy some conditions. How can k be given? Isn't that value depends on the graph? Let's take a digraph with two strongly connected components for example, and let's call them C1 and C2. Let's assume that there is an edge from C1 to C2. In this case k has to be 1. For any other given k there is no such set that satisfy the given conditions. Or am I misunderstanding something? Appreciate it if you can clarify.

Thanks!