Graph Problem

Revision en3, by TheCreator, 2024-09-08 20:46:47

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)