Graph Problem
Difference between en2 and en3, changed 0 character(s)
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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English TheCreator 2024-09-08 20:46:47 0 (published)
en2 English TheCreator 2024-09-08 18:54:32 60 (saved to drafts)
en1 English TheCreator 2024-09-08 17:15:45 526 Initial revision (published)