Integral Symmetric 2-Commodity Flows

Aubin Jarry (1)

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications

Let $G=(V,A)$ be a symmetric digraph, and $\kappa:A\rightarrow\mathbb{N}$ be a symmetric capacity. Let $s_1,s_2,t_1,t_2\in V$ and $v_1,v_2\in\mathbb{N}$. An integral symmetric 2-commodity flow in $G$ from $(s_1,s_2)$ to $(t_1,t_2)$ of value $(v_1,v_2)$ is an integral 4-commodity flow from $(s_1,t_1,s_2,t_2)$ to $(t_1,s_1,t_2,s_2)$ of value $(v_1,v_1,v_2,v_2)$. The Integral Symmetric 2-Commodity Flow Problem consists in finding a symmetric 2-commodity flow $(f_1,f_{-1},$ $f_2,f_{-2})$ from $(s_1,t_1)$ to $(s_2,t_2)$ of value $(v_1,v_2)$ such that $\Sigma f_i\leq\kappa$. It is known that the Integral 2-Commodity Flow Problem is NP-complete for both directed and undirected graphs (\cite{FHW80} and \cite{EIS76}). We prove that the cut criterion is a necessary and sufficient condition for the existence of a solution to the Integral Symmetric 2-Commodity Flow Problem, and give a polynomial-time algorithm in that provides a solution to this problem. The time complexity of our algorithm is \textbf{$6C_{flow}+O(|A|)$}, where $C_{flow}$ is the time complexity of your favorite flow algorithm (usually in $O(|V|\times|A|)$).

Mots clés: DISJOINT PATHS; MULTIFLOW; COMMODITY; FLOW; INTEGER; SYMMETRIC; GRAPH

Domaines: Autre [cs.OH]

Aubin Jarry. Integral Symmetric 2-Commodity Flows. RR-4622, INRIA. 2002. ⟨inria-00071963⟩