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.
there is no 1--4 edges,, may be ans should be 2 instead of 3
[1, 2] and [2, 4] are still there so all these three nodes 1, 2 and 4 are connected
I might be wrong, but what i can think of is that we can create a Disjoint set and union all the nodes in the given set, then traverse through the edges and check for each edge if they are already united or not, if not, we can count it as a possible removal.
I'm not sure about my answer. but I think you can call the BFS algorithm starting from one of the nodes in k. then it gives you a BFS tree, which we know has n-1 edges. Then on each step, you can delete one of the leaves if it's not in k (and also the edge connected to it) until all remaining leaves are in k. In the end, we have remaining edges r. and the answer would be m — r. I again need to say that I'm not sure about the answer. I just hope it gives you an idea to solve the problem
There could be many BFS tree.
in the example you said by removing [1,3], [3,4] and [1,4], there is no [1,4] edge in the input, so then how did you removed it(also can you give the link of the problem if it has one)
we didn't delete edge [1, 2] and [2, 4] so all nodes [1, 2, 4] are connected.
i mean in the input edges [[1 2], [1 3],[2 4],[3 4]], the isn't a [1 4] edge to be removed.
Auto comment: topic has been updated by TheCreator (previous revision, new revision, compare).
you should probably give the bounds lmao
For each node in $$$S$$$ you could calculate shortest distances between all of the $$$K$$$ nodes, but that is already quadratic complexity (running BFS $$$K$$$ times, for example).
Then, you can work with a complete graph of $$$K$$$ nodes and build a MST (length of each edge between 2 nodes in $$$S$$$ is distance between them). The answer then is difference between number of all edges $$$M$$$ and weight of your MST (actually it looks like this won't work, because you could count some edges twice D:).
If you are looking for sub quadratic time complexity, then you probably need to use some more advanced algorithms and DS. Or maybe you can get away with not calculating all shortest distances in $$$S$$$.
my thought is to use multisource bfs + dsu
multisource bfs from each black node (im calling nodes from S "black"), and for each edge keep track of the starting black node that it originated from as well as the parent edge
whenever an edge E gets visited from two different black nodes A,B, we merge these two black nodes in the dsu and we also push all of the edges on the path from E to A and all the edges on the path from E to B into our edge list (which will be the edges we cannot remove)
i believe this should work in linear time, but i might be a bit high so please tell me if any part doesnt make sense
Isn't this Steiner Tree Problem and it's NP-hard?