<p><a href="http://dl.acm.org/citation.cfm?id=1382492" rel="nofollow noreferrer">Even, Itai, and Shamir</a> 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.):
<img src="https://i.sstatic.net/5htOA.jpg" alt=""></p>

CC BY-SA 3.0
2014-04-09T06:53:02.103Z
Thanks @Andreas, but I'm wondering if the same is true even if all edge costs (and capacities) are 1.
R B
CC BY-SA 3.0
2014-04-09T06:58:48.290Z
Don't all edges have capacity one in this instance ?
Suresh Venkat
CC BY-SA 3.0
2014-04-09T08:06:49.110Z
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".
R B
CC BY-SA 3.0
2014-04-09T09:04:32.220Z
I'm afraid I still don't understand what you are asking for.
Andreas Björklund
CC BY-SA 3.0
2014-04-10T09:06:55.703Z
@AndreasBjörklund - is the same true for digraphs?
R B
CC BY-SA 3.0
2014-04-10T12:47:25.693Z
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.
Andreas Björklund
CC BY-SA 3.0
2014-04-09T06:47:47.617Z
2014-04-09T07:20:03.300Z
2014-04-09T07:20:03.300Z
Andreas Björklund
<p>Suppose that we have a two commodities flow network $N=&lt;G=(V,E), s_1,s_2,t_1,t_2\in V&gt;$.</p>

<p>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$.</p>

<p><strong>All edges has capacities 1 and cost 1.</strong></p>

<p>(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)$ ).</p>

<p>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: <strong>Is there be a network with my specifications that doesn't have an optimal integer solution?</strong></p>

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

<p><img src="https://i.sstatic.net/mV9wF.jpg" alt="enter image description here"></p>

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

<hr>

<p>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)</p>

CC BY-SA 3.0
2014-04-03T17:14:26.497Z
My understanding is that the integer problem is NP-hard even in the 2-commodity case.
Suresh Venkat
CC BY-SA 3.0
2014-04-03T17:15:22.697Z
@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.
R B
CC BY-SA 3.0
2014-04-09T14:41:41.870Z
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.
Chandra Chekuri
<multicommodity-flow><flow-problems>
Can the optimal minimum cost two-commodities flow be fractional on this special case?
R B
# Can the optimal minimum cost two-commodities flow be fractional on this special case?

(Asked by: username_0 on 2014-04-03)

Suppose that we have a two commodities flow network $N=$.

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](https://i.sstatic.net/mV9wF.jpg)

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)

**Tags:** multicommodity-flow, flow-problems
> **Comments:**
> **username_1**: My understanding is that the integer problem is NP-hard even in the 2-commodity case.  
> **username_0**: @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.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2014-04-09. Score: 4 | Accepted answer

[Even, Itai, and Shamir](http://dl.acm.org/citation.cfm?id=1382492) 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.):
![](https://i.sstatic.net/5htOA.jpg)

> **Comments:**
> **username_0**: Thanks @Andreas, but I'm wondering if the same is true even if all edge costs (and capacities) are 1.  
> **username_1**: Don't all edges have capacity one in this instance ?  
> **username_0**: 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".  
> **username_3**: I'm afraid I still don't understand what you are asking for.  
> **username_0**: @AndreasBjörklund - is the same true for digraphs?  
> **username_3**: 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.  

---

