2
$\begingroup$

Suppose that we have a two commodities flow network $N=<G=(V,E), s_1,s_2,t_1,t_2\in V>$.

The problem is to find a minimum cost two-commodity flow in which there a flow $f_1$ from $s_1$ to $t_1$ of 2 units and a flow $f_2$ from $s_2$ to $t_2$.

All edges has capacities 1 and cost 1.

(In two-commodity flow the two flows share the edges capacities, that is $\forall e\in E, f_1(e)+f_2(e)\leq 1$, and the cost is defined as $\Sigma_{_{e\in E}}f_1(e) + f_2(e)$ ).

In the general case, multi-commodity flow can have fractional optimum flow even if the capacities/costs are integers, but I was wondering if there's an example for it which doesn't use negative weights and only 2 commodities, so my question is: Is there be a network with my specifications that doesn't have an optimal integer solution?

The following example (taken from Idan Maor's presentation) shows that that 3-MCF can have only a fractional optimal flow:

enter image description here

I have two motivations here: if such network exists, it can be used to show a very simple example for which using LP for solving this problem can't work, and if there isn't such network, this might allow us to develop an efficient method for finding disjoint paths in a graph (if we can find the optimal solution in poly time).


Edit: as Suresh have mentioned, 2-commodity flow is NP-hard in the general case, so I'm only looking at the unit capacities/costs case, which I couldn't find a mentioning for it as being NP-hard (Intuitively, I believe an integer solution does exist for every such network)

$\endgroup$
  • $\begingroup$ My understanding is that the integer problem is NP-hard even in the 2-commodity case. $\endgroup$ – Suresh Venkat Apr 3 '14 at 17:14
  • $\begingroup$ @SureshVenkat - that is correct, but I couldn't find any reference for 2-commodity flow with unit costs/capacities, which is all I need for the disjoint paths. Alternatively, I could ask (although not completely equivalent) is there a case of such networks for which the resulting constraints matrix A is not totally-unimodular. $\endgroup$ – R B Apr 3 '14 at 17:15
  • 2
    $\begingroup$ It is helpful to look at Schrijver's book on combinatorial optimization (Volume C) on multiflows. These problems have been considered for a long time. $\endgroup$ – Chandra Chekuri Apr 9 '14 at 14:41
3
$\begingroup$

Even, Itai, and Shamir proved that the undirected integral two-commodity flow is NP-hard even if all capacities are one. As far as I understand, the following is an example of what you ask for. It has a fractional solution twice as large as the integer one (All edge capacities are one. The costs don't really matter, as they only come in play to break ties between several optimum flows.):

$\endgroup$
  • $\begingroup$ Thanks @Andreas, but I'm wondering if the same is true even if all edge costs (and capacities) are 1. $\endgroup$ – R B Apr 9 '14 at 6:53
  • 2
    $\begingroup$ Don't all edges have capacity one in this instance ? $\endgroup$ – Suresh Venkat Apr 9 '14 at 6:58
  • $\begingroup$ I'm not looking for integral max flow of two commodities. I'll try to rephrase what I'm looking for: Graph with two pairs of vertices $s_1,t_1,s_2,t_2$. We need to deliver $d_1,d_2$ units of flow from $s_1$ to $t_1$ and from $s_2$ to $t_2$ respectively. All weights are 1 and capacities are 1, which means that an integral flow is equivalent to edge-disjoint $d_1$ paths from $s_1$ to $t_1$ and $d_2$ paths between $s_2$ and $t_2$. My question can be phrased as: "Does the LP relaxation of this problem always have an integral solution". $\endgroup$ – R B Apr 9 '14 at 8:06
  • $\begingroup$ I'm afraid I still don't understand what you are asking for. $\endgroup$ – Andreas Björklund Apr 9 '14 at 9:04
  • 1
    $\begingroup$ Yes, there is a simple well-known gadget that replaces an undirected edge with 5 arcs and two additional vertices, so that the same fractional flow is optimal. $\endgroup$ – Andreas Björklund Apr 10 '14 at 12:47

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.