TheCreator's blog

Graph Problem
By TheCreator, history, 9 days ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

there is no 1--4 edges,, may be ans should be 2 instead of 3

→ Reply
  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    [1, 2] and [2, 4] are still there so all these three nodes 1, 2 and 4 are connected

    → Reply
»
9 days ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

→ Reply
»
8 days ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    we didn't delete edge [1, 2] and [2, 4] so all nodes [1, 2, 4] are connected.

    → Reply
    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i mean in the input edges [[1 2], [1 3],[2 4],[3 4]], the isn't a [1 4] edge to be removed.

      → Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by TheCreator (previous revision, new revision, compare).

→ Reply
»
8 days ago, # |
  Vote: I like it +5 Vote: I do not like it

you should probably give the bounds lmao

→ Reply
»
8 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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$$$.

→ Reply
»
8 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 days ago, # |
  Vote: I like it +27 Vote: I do not like it

Isn't this Steiner Tree Problem and it's NP-hard?

→ Reply