Minimum set of vertices that allow reaching all other vertices in max. one edge
graph, minimum, vertices
Solution
I think it's the Dominating Set Problem, closely related to the normal set cover problem
Problem
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!