I have an undirected simple graph and an integer x. My goal is to remove x edges from the graph so the largest connected component of the graph after the removal will be minimal.
I tried to think how to solve this problem, and i thought maybe using Girvan-Newman algorithm for removing edges with highest Betweenness. Works but very time consuming (running betweenness each round).
Any suggestions or other ideas how to tackle this problem?