0
$\begingroup$

I am interested in whether a graph (say, a complete graph) with one capacity negative (or many, but one should suffice) can be reconstructed as a graph with all non-negative capacities where the max flow between vertices of the original graph can be identified with max flows between vertices of the new graph. It is ok for the new graph to have more vertices than the original graph. Said another way, consider a complete graph K-n with additional external edges in addition attached to source/sinks. Allow one of the edges of the complete graph to have negative capacity. Can I replace the complete graph with another graph with only positive capacities such that the max flow between all possible subsets of the external sources/sinks remains the same?

CLARIFICATION: We connect each vertex of the complete graph to a distinct external vertex with an edge. If it helps, picture a complete K_6 drawn as a hexagon with an additional edge coming out of each vertex of the hexagon to 6 extra distinct vertices. Those distinct vertices are the s and t's that we are interested in considering. The edges that are not edges of the complete graph that we add are the external edges. I am interested only in cases where the original graph is the complete graph, though edges are allowed to have weight 0 or weight infinity. I hope this helps.

Thanks, Ning

$\endgroup$
  • $\begingroup$ I can't understand what you are asking. What do you mean by reconstructed? What do you mean by "max flow between vertices"? Normally we identify a specific pair of vertices $s,t$ and ask for the max flow from $s$ to $t$. What do you mean by external edges? Are you interested in only the case where the original graph is the complete graph? What do you mean by subsets of sources/sinks? Please edit your question to clarify. $\endgroup$ – D.W. Mar 5 '15 at 8:32
  • $\begingroup$ Hi; Ok, good. We connect each vertex of the complete graph to a distinct external vertex with an edge. If it helps, picture a complete K_6 drawn as a hexagon with an additional edge coming out of each vertex of the hexagon to 6 extra distinct vertices. Those distinct vertices are the s and t's that we are interested in considering. The edges that are not edges of the complete graph that we add are the external edges. I am interested only in cases where the original graph is the complete graph, though edges are allowed to have weight 0 or weight infinity. I hope this helps. $\endgroup$ – Ning Bao Mar 5 '15 at 17:15
  • 2
    $\begingroup$ I encourage you to edit your question to clarify all of these points. Comments exist only to help you improve your question. See the help center for more on how to use this site (this is not a discussion forum, so the site format might be a little different from what you are used to). $\endgroup$ – D.W. Mar 5 '15 at 19:20
1
$\begingroup$

If you indeed have an edge $e$ with a negative capacity, and, I assume, it is a directed edge having no corresponding opposite edge, then you can reverse $e$, make its capacity positive, and, then, solve a regular max-flow problem with all capacities being non-negative. (Look at the concept of the residual network to understand what a negative capacity means.) Make sure you are not confusing edge capacities with costs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.