computer_jock's blog

minimum nodes to remove to make graph completely disconnected
By computer_jock, history, 17 months ago, In English

given a undirected graph ( n nodes , m edges ) , find minimum no. of nodes to remove for making graph completely disconnected ?

constraints — n upto 1000

A greedy way could be start removing the maximum degree nodes untill graph becomes disconnected, is there a proof it would work ?

also i think its related to menger's algorithm , but that gives vertex cut for making 2 nodes disconnected , here we have to disconnect all nodes from each other..

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
17 months ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

Removing a vertex removes all edges connected to it, right?

Notice that to make the graph disconnected, you need to remove every edge. The only way to remove an edge is by removing one of the vertices its connecting. So we need to find the smallest set of vertices such that they "cover" every edge. This is known as the Minimum Vertex Cover Problem which is NP-hard in general graphs.

In bipartite graphs, the problem can be solved using flow.

Please correct me if I misunderstood the problem.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for explanation. can you share implementation for bipartite graphs ?

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      According to König's theorem, the number of vertices in the minimum vertex cover is equal to the number of edges in the maximum matching of any bipartite graph. Thus, we can find the size of the minimum vertex cover by finding the maximum matching of the graph (actually finding the vertices is possible but harder).

      This is a standard problem that can be solved using maximum flow algorithms. If you don't know about maximum flow, you can read about it in the Competitive Programmer's Handbook — Chapter 20 (20.1 and 20.3). For implementation of the Ford-Fulkerson and Edmonds-Karp-algorithms, you can see this page from CP-Algorithms.

      You can also see this page, also from CP-Algorithms, for explanation and implmentation of Kuhn's algorithm — an algorithm that solves maximum matching in bipartite graphs without talking about flows. As far as I have understood, behind the scenes Kuhn's algorithm works in basically the same way as the flow algorithms I mentioned. It may be faster than the flow algorithms by a constant factor since it is specifically designed for calculating maximum matching, but the time complexity is the same — $$$O(VE)^\dagger$$$.

      If you need a faster algorithm for calculating the maximum matching in a bipartite graph, you can use the Hopcroft-Karp-algorithm to do that in $$$O(E\sqrt{V})$$$.

      $$$^\dagger$$$ All sites I linked say that the time complexities of the Ford-Fulkerson and Edmonds-Karp-algorithms are slower than $$$O(VE)$$$. This is true in general flow networks, but both of these algorithms work in $$$O(VE)$$$ in flow networks where all capacities are $$$1$$$, as is the case in the maximum matching flow network.

      P.S. It may be possible that faster implementations exist elsewhere

      → Reply
»
17 months ago, # |
  Vote: I like it +6 Vote: I do not like it

It is also equivalent to the maximum independent set problem (which also is NP-Hard). Because when you remove the minimum number of nodes to make the graph disconnected, all the nodes that haven't been removed will be a maximum independent set.

So most likely there is no greedy algorithm for this problem. Your greedy algorithms fails for example for this graph:

Spoiler
→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here you can see the detailed approach .. Striver sir has explained

https://youtu.be/q4Ps6cdrnw4

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    That's not the same problem. The video you linked consideres removing edges, while OP asked about removing vertices.

    → Reply