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?

  • 2
    $\begingroup$ This certainly looks like an NP-complete problem, swims like an NP-complete problem and quacks like an NP-complete problem... $\endgroup$ – Tom van der Zanden Jan 20 '16 at 20:45
  • $\begingroup$ @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.) ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Jan 20 '16 at 20:55
  • 2
    $\begingroup$ @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? $\endgroup$ – David Richerby Jan 20 '16 at 21:32
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Jan 21 '16 at 19:21
  • 1
    $\begingroup$ You can take a look at the NP hardness of minimum bisection for inspiration (or even try a reduction). $\endgroup$ – Yuval Filmus Jan 21 '16 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.