Quadratic assignment problems on series-parallel digraphs

Christofides has shown that the quadratic assignment problem (QAP) on isomorphic trees is solvable in polynomial time by dynamic programming. We generalize the approach to minimal series-parallel digraphs and show that this problem is equivalent to the general QAP, thus NP-hard. However the restriction to the subclass of series-parallel digraphs not containing bipartite subgraphs again is solvable in polynomial time. An algorithm for this class is given.This work was financially supported by the Austrian Fonds zur Förderung der wissenschaftlichen Forschung, Projekt S32/01.