Given an **undirected connected** graph with _N_ vertices and _M_ edges, and a set _S_ of _K_ nodes of this graph.↵
↵
Find the **maximum number** of edges that we can remove from the graph such that all these K nodes still remains connected (i.e there exist one component which has all these K nodes )↵
↵
eg -:↵
edges -:[[1 2], [1 3],[2 4],[3 4]]↵
S = [1, 2, 4]↵
↵
We can remove maximum of 3 edges [1, 3] and [3, 4] and [1, 4], removing any other edges makes given set of nodes disconnected.↵
↵
↵
How to solve this ?↵
↵
↵
I can only think of trying all 2^m subset of edges.
↵
Find the **maximum number** of edges that we can remove from the graph such that all these K nodes still remains connected (i.e there exist one component which has all these K nodes )↵
↵
eg -:↵
edges -:[[1 2], [1 3],[2 4],[3 4]]↵
S = [1, 2, 4]↵
↵
We can remove maximum of 3 edges [1, 3] and [3, 4] and [1, 4], removing any other edges makes given set of nodes disconnected.↵
↵
↵
How to solve this ?↵
↵
↵
I can only think of trying all 2^m subset of edges.
