We are given a connected graph (here is an example)
We want to find all the smallest set of vertices such that when any vertex in the graph is cut, we can traverse from any remaining point in the graph to a member of the set
In this example, one such smallest set is circled. If you disconnect the graph at any of the articulation points (points with multiple colors on the graph) you can still reach one of the circled vertices from any other point.
My approach was to find all the articulation points (points with two colors on the graph) using Tarjan's algorithm. Then once you found all the articulation points, cut the graph at each one and use a dfs to find all the remaining connected components. Finally, we compile all the different connected components and try to select the set of vertices from there.
However, this turns into a minimum hitting set problem, which is NP. Is there a way to find this set of points in polynomial time?