MAXIMUM INTEGRAL K-MULTICOMMODITY FLOW ON TREES

• INSTANCE: A tree $T=\left(V,E\right)$, a capacity function $c : E \rightarrow N$ and k pairs of vertices $(s_i,t_i)$.

• SOLUTION: A flow $f_i$ for each pair $(s_i,t_i)$ with $f_i \in N$ such that, for each $e\in E$, $\sum_{i=1}^k f_iq_i(e) \leq c(e)$ where $q_i(e)=1$ if e belongs to the unique path from $s_i$ and $t_i$, 0 otherwise.

• MEASURE: The sum of the flows, i.e., $\sum_{i=1}^kf_i$.

  
  

• Good News: Approximable within 2 [190].

• Bad News: APX-complete [190].

• Comment: Transformation from MAXIMUM 3-DIMENSIONAL MATCHING. It remains APX-complete even if the edge capacities are 1 and 2.