<p>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.</p>

CC BY-SA 2.5
2010-11-05T18:42:14.567Z
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?
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-05T18:57:53.527Z
I have fixed the question according to your suggestions.Thank you
YAKOVM
CC BY-SA 2.5
2010-11-05T19:04:09.913Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-05T19:46:59.847Z
Its undirected graph.I have changed the question
YAKOVM
CC BY-SA 2.5
2010-11-05T20:04:26.570Z
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.
Suresh Venkat
CC BY-SA 2.5
2010-11-05T20:10:23.890Z
Undirected + strongly connected doesn't make sense, you should remove "strongly". Anyway, clique seems to reduce to this problem, so we won't get any quick algorithm.
Karolina Sołtys
CC BY-SA 2.5
2010-11-05T20:11:10.503Z
@Suresh - I think we ask for an induced subgraph.
Karolina Sołtys
CC BY-SA 2.5
2010-11-05T20:23:39.503Z
I have to think about it.I will change the question shortly
YAKOVM
CC BY-SA 2.5
2010-11-05T20:43:55.833Z
@Karolina good point. I need to read these questions more carefully.
Suresh Venkat
CC BY-SA 2.5
2010-11-05T21:01:25.883Z
What's $n$? Often it is the number of vertices in the graph in question but I'm guessing that in your question $n$ is an input integer; is that right?
Warren Schudy
CC BY-SA 2.5
2010-11-05T21:09:15.767Z
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?
Warren Schudy
CC BY-SA 2.5
2010-11-06T04:20:52.537Z
Although @Warren and @Karolina have good points, sometimes applications only need rather small values of n to get interesting results. Often values of around n=10 can be interesting and are still achievable in practice, simply by doing slightly intelligent variants of brute force, even without some other property (high girth, low treewidth, etc) that would give a better asymptotic guarantee. However, since the question doesn't mention any particular application, it's hard to say whether this is relevant.  Yakov: it would be interesting to know what application you have in mind.
Joshua Grochow
CC BY-SA 2.5
2010-11-07T06:24:52.767Z
Voted to close. As Suresh and Karolina stated, the question as is stated in revision 3 does not make sense. The asker said that he/she would modify the question shortly, but the problem has not been addressed for one day. As Joshua said, the question might be potentially interesting even if the underlying problem is NP-hard, but the current question is not specific enough for that.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-08T00:12:23.847Z
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
Suresh Venkat
<ds.algorithms><graph-theory><graph-algorithms>
Identifying sub graph in connected digraph
YAKOVM
# Identifying sub graph in connected digraph

(Asked by: username_0 on 2010-11-05)

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.

**Tags:** ds.algorithms, graph-theory, graph-algorithms
> **Comments:**
> **username_1**: 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?  
> **username_0**: I have fixed the question according to your suggestions.Thank you  
> **username_1**: 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.  
> **username_0**: Its undirected graph.I have changed the question  
> **username_2**: 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.  
> **username_3**: Undirected + strongly connected doesn't make sense, you should remove "strongly". Anyway, clique seems to reduce to this problem, so we won't get any quick algorithm.  
> **username_3**: @Suresh - I think we ask for an induced subgraph.  
> **username_0**: I have to think about it.I will change the question shortly  
> **username_2**: @Karolina good point. I need to read these questions more carefully.  
> **username_4**: What's $n$? Often it is the number of vertices in the graph in question but I'm guessing that in your question $n$ is an input integer; is that right?  
> **username_4**: 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?  
> **username_5**: Although @Warren and @Karolina have good points, sometimes applications only need rather small values of n to get interesting results. Often values of around n=10 can be interesting and are still achievable in practice, simply by doing slightly intelligent variants of brute force, even without some other property (high girth, low treewidth, etc) that would give a better asymptotic guarantee. However, since the question doesn't mention any particular application, it's hard to say whether this is relevant.  Yakov: it would be interesting to know what application you have in mind.  
> **username_1**: Voted to close. As Suresh and Karolina stated, the question as is stated in revision 3 does not make sense. The asker said that he/she would modify the question shortly, but the problem has not been addressed for one day. As Joshua said, the question might be potentially interesting even if the underlying problem is NP-hard, but the current question is not specific enough for that.  
> **username_2**: 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  

---

## 0 answers

