<p>The problem is at least as hard the maximum edge-disjoint paths problem (MEDP) since we can set $d(i) = 1$ for each pair. The approximability of MEDP has been investigated extensively and in particular it is known that MEDP in directed graphs is hard to approximate to within a factor of $m^{1/2-\epsilon}$ (technically it is $n^{1/2-\epsilon}$ since the graphs are sparse). This was shown in a paper of Guruswami etal. <a href="http://www.sciencedirect.com/science/article/pii/S0022000003000667" rel="nofollow">http://www.sciencedirect.com/science/article/pii/S0022000003000667</a>. Roughly at the same time there was another paper by Ma and Wang established hardness of $2^{\log^{1-\epsilon} n}$ for <em>acyclic</em> graphs. More recent work by Chuzhoy etal showed hardness results even with congestion allowed; my understanding is that the hardness holds even for instances that are acyclic and these results are stronger than the one by Ma and Wang, however, one should look more carefully at the paper to make sure or ask the authors. </p>

CC BY-SA 3.0
2012-02-09T17:36:19.950Z
Thank you sir:@chandra chekuri. I have one minor confusion though: Is MEDP not different from this problem for eg., say we have 2 commodities((s1,t1),(s2,t2)) and d1 & d2>>1 and unit capacities. Also is the above problem on undirected graphs with only two commodities is hard to approximate?
vikku
CC BY-SA 3.0
2012-02-09T22:30:05.083Z
Well, MEDP is a special case of your problem so any hardness for MEDP will translate into hardness for the more general problem. If $k$ is small then one can always get a $1/k$-approximation via simple max-flow although the problem may be NP-Hard. It is known that your problem is NP-Hard for k=3 in undirected graphs. You can look at Schrijver's book on Combinatorial Optimization (Volume C on multiflows for some of these NP-Hardness results).
Chandra Chekuri
CC BY-SA 3.0
2012-12-10T11:19:35.103Z
MEDP is solvable in $O(n^{k+1})$ in DAG for $k$ pairs.
Saeed
CC BY-SA 3.0
2012-02-09T16:03:52.767Z
2012-02-09T16:03:52.767Z
Chandra Chekuri
<p>I am faced with the following question on max. integer multiflow:</p>
<blockquote>
<p>INSTANCE: An acyclic directed graph G=(V,E), a capacity function c:E→N, k pairs of vertices (si,ti) and a demand function d:{1,…,k}→N.</p>
<p>Objective: Find the integer flows satisfying maximum demand.</p>
</blockquote>
<p>what is the hardness status of this problem?</p>

<cc.complexity-theory><graph-theory><max-flow><multicommodity-flow>
multi-commodity flow acyclic digraphs
vikku
# multi-commodity flow acyclic digraphs

(Asked by: username_0 on 2012-02-09)

I am faced with the following question on max. integer multiflow:

> INSTANCE: An acyclic directed graph G=(V,E), a capacity function c:E→N, k pairs of vertices (si,ti) and a demand function d:{1,…,k}→N.
>
> Objective: Find the integer flows satisfying maximum demand.

what is the hardness status of this problem?

**Tags:** cc.complexity-theory, graph-theory, max-flow, multicommodity-flow


---

## 1 answers

### Answer by username_1 on 2012-02-09. Score: 4

The problem is at least as hard the maximum edge-disjoint paths problem (MEDP) since we can set $d(i) = 1$ for each pair. The approximability of MEDP has been investigated extensively and in particular it is known that MEDP in directed graphs is hard to approximate to within a factor of $m^{1/2-\epsilon}$ (technically it is $n^{1/2-\epsilon}$ since the graphs are sparse). This was shown in a paper of Guruswami etal. <http://www.sciencedirect.com/science/article/pii/S0022000003000667>. Roughly at the same time there was another paper by Ma and Wang established hardness of $2^{\log^{1-\epsilon} n}$ for *acyclic* graphs. More recent work by Chuzhoy etal showed hardness results even with congestion allowed; my understanding is that the hardness holds even for instances that are acyclic and these results are stronger than the one by Ma and Wang, however, one should look more carefully at the paper to make sure or ask the authors.

> **Comments:**
> **username_0**: Thank you sir:@chandra chekuri. I have one minor confusion though: Is MEDP not different from this problem for eg., say we have 2 commodities((s1,t1),(s2,t2)) and d1 & d2>>1 and unit capacities. Also is the above problem on undirected graphs with only two commodities is hard to approximate?  
> **username_1**: Well, MEDP is a special case of your problem so any hardness for MEDP will translate into hardness for the more general problem. If $k$ is small then one can always get a $1/k$-approximation via simple max-flow although the problem may be NP-Hard. It is known that your problem is NP-Hard for k=3 in undirected graphs. You can look at Schrijver's book on Combinatorial Optimization (Volume C on multiflows for some of these NP-Hardness results).  
> **username_2**: MEDP is solvable in $O(n^{k+1})$ in DAG for $k$ pairs.  

---

