We have a graph with connections to vertices given to us. For example, consider that following pairs of vertices are connected:
1 & 2 2 & 3 3 & 4 4 & 5 5 & 6
Now the graph becomes 1-2-3-4-5-6. Maximum vertices I can drop such that atleast one of their neighbors is still in the set, is: 4. This is because I can drop all but 2 and 5 since everything else has a connection to either 2 or 5.
I am trying to come up with an algorithm that can do this. So far, I have this algorithm:
- Get all inputs
- Find vertices with maximum connections
- Drop all other vertices
- Check if all vertices have atleast one neighbor in set
- If not, undo last drop
This algorithm is brute force and inefficient. Is there a better way to do it?