<p>This is done by using minimum cost flow. See section 17.4 <a href="http://valis.cs.uiuc.edu/~sariel/teach/notes/algos/lec/17_flow_mc_II.pdf" rel="nofollow">here</a>.</p>

CC BY-SA 2.5
2010-10-16T19:40:31.017Z
Thanks. The text is clear and I stand stupid. Sorry for bothering everyone with questions like this.
jakab922
CC BY-SA 2.5
2010-10-16T19:28:09.403Z
2010-10-16T19:28:09.403Z
Sariel Har-Peled
<p>We are given a $G(V,E)$ digraph and a $c:E \rightarrow \mathbb{R}$ weight function. We are searching for a set of $C_{1}(V_{1},E_{1}),C_{2}(V_{2},E_{2}),\ldots,C_{k}(V_{k},E_{k})$ directed circles such that $V_{1},\ldots,V_{k}$ form a partition of $V$ and $\sum_{i = 1}^{k}\sum_{e \in E_{i}}c(e)$ is minimal among all such covers. </p>

<p>I know there is a polynomial algorithm which solves this problem. I just don't know what that algorithm is. Anyone knows this problem and can give a hint or a solution?(hint preferred)</p>

CC BY-SA 2.5
2010-10-16T18:24:54.893Z
cstheory.stackexchange.com is for research-level questions and not for homework help.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-16T18:30:22.780Z
I thought it's a Q&A site for questions in the cs topic.
jakab922
CC BY-SA 2.5
2010-10-16T18:42:44.760Z
This website is for research-level questions in theoretical computer science.  [“Typical homework problems in textbooks” are off-topic here](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/235#235).  This question is at the level of typical homework problems in textbooks.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-16T18:59:15.967Z
If this is a typical homework level question can you give a short hint on how to solve it?
jakab922
CC BY-SA 2.5
2010-10-16T19:22:26.620Z
I will not give a hint because (1) I am afraid that giving a hint to this question may encourage other people to ask questions at the same level, and (2) for this problem, I find it difficult to give a hint without giving the solution.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-16T19:54:19.593Z
I second Tsuyoshi. Homework questions are not welcome here. If you want a solution for such a problem, look at textbooks or ask your course instructor/TA. Also note that in most universities, getting help in solving assignments and presenting work which is not yours can have heavy punishments. I discourage anyone from answering homework questions, specially from new/low reputation users using nicknames.
Kaveh
CC BY-SA 2.5
2010-10-16T19:54:28.460Z
I won't present this work since the deadline has passed. I was just interested in the solution. That's why I asked it...
jakab922
CC BY-SA 2.5
2010-10-16T19:56:53.640Z
You could have asked your course instructor/TA for a solution.
Kaveh
CC BY-SA 2.5
2010-10-16T20:04:47.187Z
Yeah but the next class is on next friday.
jakab922
CC BY-SA 2.5
2010-10-16T21:23:22.180Z
I have to disagree. I think many people do not know about min-cost flow since it is not a standard topic covered in standard algorithms class.
Sariel Har-Peled
CC BY-SA 2.5
2010-10-16T21:25:22.397Z
@Sariel: What is the _easiest_ solution depends on how your learn these algorithms, but in my opinion, reducing this problem to the minimum-cost flow is a more complicated way to solve it than necessary.  In fact, if it required the minimum-cost flow, I might not have voted to close this question.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-16T21:31:04.743Z
@Sariel: By the way, if you would like to discuss more about closing/reopening, please start a thread on [Meta](http://meta.cstheory.stackexchange.com/).  Continuing a discussion in comments is not recommended.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-16T21:45:50.660Z
@Sariel Har-Peled: I am just guessing, but I think the instructor had thought that students can solve it based on the material covered in the course. Btw, there is a meta-discussion on [homework questions](http://meta.cstheory.stackexchange.com/questions/209/homework-or-things-that-look-like-homework). (ps: I found the book very interesting, thanks for the link.)
Kaveh
CC BY-SA 2.5
2010-10-17T00:01:26.613Z
@Tsuyoshi. Exactly my point. If there is a solution that does not use min cost flow (or circulations), I would like to know about it.
Sariel Har-Peled
CC BY-SA 2.5
2010-10-18T15:11:54.537Z
You can use something somewhat simpler than flow/circulations, namely matching
daveagp
<ds.algorithms>
Minimal directed circles partition cover of a directed graph
jakab922
# Minimal directed circles partition cover of a directed graph

(Asked by: username_0 on 2010-10-16)

We are given a $G(V,E)$ digraph and a $c:E \rightarrow \mathbb{R}$ weight function. We are searching for a set of $C\_{1}(V\_{1},E\_{1}),C\_{2}(V\_{2},E\_{2}),\ldots,C\_{k}(V\_{k},E\_{k})$ directed circles such that $V\_{1},\ldots,V\_{k}$ form a partition of $V$ and $\sum\_{i = 1}^{k}\sum\_{e \in E\_{i}}c(e)$ is minimal among all such covers.

I know there is a polynomial algorithm which solves this problem. I just don't know what that algorithm is. Anyone knows this problem and can give a hint or a solution?(hint preferred)

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: cstheory.stackexchange.com is for research-level questions and not for homework help.  
> **username_0**: I thought it's a Q&A site for questions in the cs topic.  
> **username_1**: This website is for research-level questions in theoretical computer science.  [“Typical homework problems in textbooks” are off-topic here](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/235#235).  This question is at the level of typical homework problems in textbooks.  
> **username_0**: If this is a typical homework level question can you give a short hint on how to solve it?  
> **username_1**: I will not give a hint because (1) I am afraid that giving a hint to this question may encourage other people to ask questions at the same level, and (2) for this problem, I find it difficult to give a hint without giving the solution.  
> **username_2**: I second Tsuyoshi. Homework questions are not welcome here. If you want a solution for such a problem, look at textbooks or ask your course instructor/TA. Also note that in most universities, getting help in solving assignments and presenting work which is not yours can have heavy punishments. I discourage anyone from answering homework questions, specially from new/low reputation users using nicknames.  
> **username_0**: I won't present this work since the deadline has passed. I was just interested in the solution. That's why I asked it...  
> **username_2**: You could have asked your course instructor/TA for a solution.  
> **username_0**: Yeah but the next class is on next friday.  
> **username_3**: I have to disagree. I think many people do not know about min-cost flow since it is not a standard topic covered in standard algorithms class.  
> **username_1**: @Sariel: What is the _easiest_ solution depends on how your learn these algorithms, but in my opinion, reducing this problem to the minimum-cost flow is a more complicated way to solve it than necessary.  In fact, if it required the minimum-cost flow, I might not have voted to close this question.  
> **username_1**: @Sariel: By the way, if you would like to discuss more about closing/reopening, please start a thread on [Meta](http://meta.cstheory.stackexchange.com/).  Continuing a discussion in comments is not recommended.  
> **username_2**: @username_3: I am just guessing, but I think the instructor had thought that students can solve it based on the material covered in the course. Btw, there is a meta-discussion on [homework questions](http://meta.cstheory.stackexchange.com/questions/209/homework-or-things-that-look-like-homework). (ps: I found the book very interesting, thanks for the link.)  
> **username_3**: @Tsuyoshi. Exactly my point. If there is a solution that does not use min cost flow (or circulations), I would like to know about it.  
> **username_4**: You can use something somewhat simpler than flow/circulations, namely matching  

---

## 1 answers

### Answer by username_3 on 2010-10-16. Score: 2 | Accepted answer

This is done by using minimum cost flow. See section 17.4 [here](http://valis.cs.uiuc.edu/~sariel/teach/notes/algos/lec/17_flow_mc_II.pdf).

> **Comments:**
> **username_0**: Thanks. The text is clear and I stand stupid. Sorry for bothering everyone with questions like this.  

---

