0
$\begingroup$

Suppose we have a complete graph, with say 100 nodes. We divide the nodes in the graph into groups, for example 10 nodes in each group, identified by color. We want to obtain a minimum spanning tree under the constraint that at least one node will be present from each group ("group spanning tree").

How to write an efficient algorithm for this, making sure it is a tree (no cycles), without iterating over the entire node set, on every pass checking presence of cycles, and also making sure that at least one node from each group is represented?

Improve this question
$\endgroup$
1
  • $\begingroup$ As noted by vonbrand, your problem is unclear. Can you copy the actual problem statement? $\endgroup$
    – Yuval Filmus
    Apr 21, 2020 at 9:47

3 Answers 3

Reset to default
2
$\begingroup$

A spanning tree connects all nodes, so in particular it connects nodes of each color.

Are you sure that is the problem you are facing?

Improve this answer
$\endgroup$
3
  • $\begingroup$ I have added minimum to it now. $\endgroup$
    – meowcat
    Apr 21, 2020 at 0:23
  • 1
    $\begingroup$ @meowcat, I don't see how that changes the point vonbrand has made. Every spanning tree satisfies the constraint "at least one node will be present from each group". $\endgroup$
    – D.W. ♦
    Apr 21, 2020 at 5:27
  • $\begingroup$ By the way, this is not an answer... better as a comment. $\endgroup$
    – Yuval Filmus
    Apr 21, 2020 at 9:48
1
$\begingroup$

It seems to be a group Steiner tree problem. See the answer by @Juno in connecting an unconnected forest of subtrees in a graph?

Improve this answer
$\endgroup$
0
$\begingroup$

I say u find the MST for a virtual graph composed of ur groups each as one node. Meaning u omit edges inside the group and treat edges to/from the outside world as connecting to the virtual node.

Think of it as post office that receives all letters coming to/from a certain district then distribute them

Improve this answer
$\endgroup$
2
  • $\begingroup$ There could be a scenario where the optimal MST may have more than one node from a group. So by discarding all the other nodes we may not end in an optimal solution $\endgroup$
    – meowcat
    Apr 21, 2020 at 19:26
  • $\begingroup$ Sorry, I'm missing something here; your defined problem accept more than one node from the same group (u said "at least" not exactly one), so where is the difference from the original MST??? u realize a MST must include all nodes, i.e. there's no case where a group is not presented by at least one node in the MST... It seems to me that the original problem wants "Exactly" (not "at least" one node from each group $\endgroup$
    – ShAr
    Apr 21, 2020 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.