# Maximum flow, where such paths as source$\to$node$\to$sink must be ignored

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).

• 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? – D.W. Oct 15 '15 at 18:21
• 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. – beginner1010 Oct 16 '15 at 3:55
• 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. – beginner1010 Oct 16 '15 at 3:55
• 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). – D.W. Oct 16 '15 at 4:07
• 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. – 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.
• 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. – beginner1010 Oct 16 '15 at 9:41