'Minimum amount of edges to remove to create k connected components in an undirected graph?

How do I approach the problem: Minimum amount of edges to remove to create k connected components? The graph might already be a forest, though not necessarily one with k connected components, and may have cycles. It is unweighted and undirected.

graphgraph-theoryconnected-components


Solution 1:[1]

If the original graph is a tree, then the removal of each edge will increase the number of connected components by 1. After removing k-1 edges, the graph will become a forest with k connected components.

Solution 2:[2]

  • If the graph already has at least k components, then the answer is 0.
  • If the graph is a tree, then the answer is k-1.
  • If the graph is the complete graph with n nodes, then the answer is n-1 + n-2 + ... + n-k+1 = (n(n-1) - (n-k)(n-k+1))/2.
  • Without assumption, the answer can be any number between 0 and (n(n-1) - (n-k)(n-k+1))/2.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Ashwin Ganesan
Solution 2 Stef

Related Questions