Hello I need some idea for a quick algorithm. Given a strongly connected undirected graph G with weighted edges, I would like to identify induced sub graph(it is required to be weakly connected) of size n vertices ,such that its weight is minimum. Thank you.

  • 3
    $\begingroup$ I guess that the problem is too underspecified. Assuming that “size n” means that the number of vertices is equal to n, what prevents you from just dropping all edges? Is the subgraph required to be strongly connected? Is the subgraph required to be an induced subgraph? Or can edge weights be negative? $\endgroup$ – Tsuyoshi Ito Nov 5 '10 at 18:42
  • 2
    $\begingroup$ I read revision 2. If the problem is really as is written, the orientation of edges is irrelevant and the input can be an undirected graph without loss of generality, if I am not mistaken. Therefore, I doubt that you are asking the right question. $\endgroup$ – Tsuyoshi Ito Nov 5 '10 at 19:04
  • 2
    $\begingroup$ if it's undirected, then the distinction between strongly and weakly connected is irrelevant, and you're asking for a minimum size connected subgraph. This is of course the minimum spanning tree. $\endgroup$ – Suresh Venkat Nov 5 '10 at 20:04
  • 4
    $\begingroup$ As Karolina indicated clique and densest subgraph reduce to your problem, so in the worst case there's not much hope for a good algorithm. Does your graph have some special property such as high girth, low treewidth, or something that might help? $\endgroup$ – Warren Schudy Nov 5 '10 at 21:09
  • 5
    $\begingroup$ Yakov, if you have any updates, please post them as a comment and flag the post for moderator attention, and we can revisit the issue of reopening $\endgroup$ – Suresh Venkat Nov 8 '10 at 0:12