How can the maximum flow of a graph be computed when all nodes of the graph are connected to both sink and source nodes (two hypothetical nodes), and the maximum flow method should ignore such paths as $\text{source} \to \text{node} \to \text{sink}$, where $\to$ is a single edge?

A valid path containing a positive flow can be $source \to v$, $v \to w$, and $w \to sink$ where $v \neq{w}$.

I am not sure whether it's helpful, but the graph is a DAG (directed acyclic graph).

  • $\begingroup$ What have you considered or tried? Have you tried seeing whether the standard Ford-Fulkerson framework can be adapted to this situation? Have you considered enumerating all such paths and then doing something with them, e.g., forming a linear program? What do you mean by "should not count such paths"? Can you give a more precise specification of the problem? Is the only requirement that the flow be decomposible into a set of paths of length $\ge 3$? What if there's one way to decompose the flow into paths of length $\ge 3$, but you can also find some path of length $<3$ in the flow? $\endgroup$ – D.W. Oct 15 '15 at 18:21
  • $\begingroup$ I wonder why those who can't solve the problem give a downvote! The original problem says, there are N seats, numbered from 1 through N. N people go to sit on the seats, and they have N tickets, numbered again from 1 through N. The person with ticket 1 comes first, the next would have ticket 2, and so forth. $\endgroup$ – beginner1010 Oct 16 '15 at 3:55
  • $\begingroup$ A person with ticket x can sit on one of those seats, whose their numbers are divisible by x. For example, a person with ticket 3 can sit on one of seats 3,6,9, .... People should sit if they can. What is the least number of people, who can sit on seats? In my solution: I built a graph, in which a connection between two numbers is established when there is a divisibility between those numbers. Then, I need to run the modified max flow method that I explained. $\endgroup$ – beginner1010 Oct 16 '15 at 3:55
  • 1
    $\begingroup$ It may be clear to you, but it's not clear to me -- for instance, I still don't see an answer to my questions about what exactly counts as a valid flow, or what you want to have happen if there are multiple ways to decompose a flow into paths. What matters most is not whether it is clear to you (or me); what matters is whether it is sufficiently clear to answerers. It's in your interests to ensure the question is clear to as many people as possible. If you believe it's already clear, that is your call (and something the community is able to vote on). $\endgroup$ – D.W. Oct 16 '15 at 4:07
  • 1
    $\begingroup$ Also, please understand that questions of the form "here is my exercise problem, I can't see how to solve it, please solve it for me" are not always well-received on this site. Different folks have different views on this, but here is one: arguably, the purpose of exercises is for you to get practice learning to solve problems, and to help you diagnose gaps in your knowledge; having us solve the exercise for you arguably serves neither of those purposes, and helps neither you nor future visitors. Just letting you know so that you can be prepared for that as a possible reaction. $\endgroup$ – D.W. Oct 16 '15 at 4:09

Let $G=(V,E)$ be some directed graph where every node $v_i$, except for the source $s$ and sink $t$, has an in-edge $(s,v_i)$ and an out-edge $(v_i,t)$.

To compute the desired flow, we can reduce the problem to a new directed graph $G'=(V',E')$, where every node of the original Graph, except for $s$ and $t$, is replaced by two new nodes $v_i'$ and $v_i''$. The source is now connected to $v_i'$ and the sink to $v_i''$. Thus, we have new edges $(s,v_i')$ and $(v_i'',t)$. Furthermore, we connect every $v_i''$ with the corresponding $v_i'$ via an edge $(v_i'',v_i')$ of very high capacity. Finally, we add an edge $(v_i',v_j'')$ for every edge $(v_i,v_j)$ of the original graph. The capacity of every edge in $G'$ is equal to its counterpart in $G$, except for the edges $(v_i'',v_i')$, wich correspond to nodes in $G$ and therefore have arbitrary high capacity.

Note that flow that enters $v_i'$ via the source can not directly escape to the sink but must traverse an edge $(v_i',v_j'')$ to another vertex $v_j''$ first. From $v_j''$ the flow can either go to the sink, or continue onwards via $v_j'$. Thus, by computing a maximum flow in $G'$ we obtain a solution for $G$ where all flow that leaves the sink must traverse at least three edges before it reaches the sink.

  • $\begingroup$ Interesting! but it does not give the correct max flow. Imagine the capacity of all source -> node and node -> sink edges are 1.It means each node can be used once at most; however, in your solution, different flows can be found in which one node has been used more than once. $\endgroup$ – beginner1010 Oct 16 '15 at 1:17
  • $\begingroup$ What do you mean by a vertex is used at most once? I don't understand your point. Maybe you can give an example. Also, maybe I should clarify that the capacities of the edges in G' correspond to their counterparts in G, except for (v'',v'), which has no corresponding edge in G. $\endgroup$ – Dennis Kraft Oct 16 '15 at 5:43
  • $\begingroup$ As I mentioned, some vertices might be used more than once in your solution although since the capacity of all edges is 1, each vertex can be used once at most. I have also implemented your solution that does not work in general. As the graph for which your method gives incorrect answer is fairly large, it is not possible to presenet it here unfortunately. The graph has 17 nodes $\endgroup$ – beginner1010 Oct 16 '15 at 8:29
  • $\begingroup$ That dosn't answer my question of what you mean by "use". If you mean that there is flow entering and exiting a vertex via different edges, then the same thing is possible in the original graph. For instance, consider the Graph G = ({s,t,u,v,w,x}, {(u,v),(w,v),(v,x)} U {"source and sink edges"}). A maximum flow that satisfies your additional constraint (which is not clearly stated at all as D.W. pointed out), would be a path s->u->v->t and another path s->w->v->x->t. Note that v was "used" twice in this maximum flow. Please be more specific. Otherwise it is impossible to help. $\endgroup$ – Dennis Kraft Oct 16 '15 at 8:54
  • $\begingroup$ Thank you for the message. Actually, I had made a premise mistakenly. I thought if the capacity of $source \to v$ is $1$ we can use vertex $v$ in the maximum flow at most once. However, as you explained it is not correct although, if I am not wrong again, you have solved what the question asks correctly. $\endgroup$ – beginner1010 Oct 16 '15 at 9:41

Your Answer

