Multiflows in symmetric digraphs

We investigate the integral multicommodity flow problem in symmetric directed graphs. In order to complete this study on symmetry, we also investigate the symmetric multicommodity flow problem, where requests are symmetric (a symmetric request is actually a pair of requests with the same required capacity and reversed endpoints).It is known that by using a specificity of symmetric digraphs, it is possible to find 2-commodity flows in polynomial time when one of the requests is of value 1. We show that this specificity does not extend to greater flow values, and prove that the 2-commodity flow problem is NP-complete.When requests are symmetric, we propose a polynomial-time algorithm that finds symmetric 2-commodity flows by using 5 simple flow computations, and prove that the symmetric 3-commodity flow problem is NP-complete.