# Choosing edges to disconnect graph

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?

• This certainly looks like an NP-complete problem, swims like an NP-complete problem and quacks like an NP-complete problem... – Tom van der Zanden Jan 20 '16 at 20:45
• @TomvanderZanden : ​ It seems far more likely to me that it would be FP$^{||}$$^{\text{F}}$$^{\text{NP}}$-complete than NP-complete. ​ ​ ​ (It's also obviously in W$[\hspace{-0.03 in}$P]O.) ​ ​ ​ ​ ​ ​ ​ ​ – user12859 Jan 20 '16 at 20:55
• @RickyDemer I can't read your comment because your manual negative spacing makes the symbols collide. How many times do we have to ask you to STOP DOING THAT? – David Richerby Jan 20 '16 at 21:32
• Try a reduction from the balanced partition problem: given a set of an even number of positive integers, can it be partitioned into two sets of equal sizes and equal sums? – Yuval Filmus Jan 21 '16 at 19:21
• You can take a look at the NP hardness of minimum bisection for inspiration (or even try a reduction). – Yuval Filmus Jan 21 '16 at 20:28