7
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – vikku
    Commented Feb 9, 2012 at 17:36
  • $\begingroup$ 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). $\endgroup$
    – Chandra Chekuri
    Commented Feb 9, 2012 at 22:30
  • $\begingroup$ MEDP is solvable in $O(n^{k+1})$ in DAG for $k$ pairs. $\endgroup$
    – Saeed
    Commented Dec 10, 2012 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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