this is probably a stupid question, but what is the canonical problem that asks for the minimum set of vertices out of a graph, so that from these vertices, all other vertices can be reached by "traveling" no more than one edge? The real-life application would be: Which people do I need to know, to be connected to everybody else on the planet by just one degree? Thanks!
I think it's the Dominating Set Problem, closely related to the normal set cover problem