Tractability frontiers of the partner units configuration problem

The partner units problem (PUP) is an acknowledged hard benchmark problem for the Logic Programming community with various industrial application fields like surveillance, electrical engineering, computer networks or railway safety systems. Although it is already known for a while that the PUP is NP-complete in its general form, complexity for subproblems reflecting the real problems in industrial fields remained widely unclear so far. In this article we provide all missing complexity results. For the subclass of the PUP that belongs to the complexity class P we present a polynomial-time algorithm and give in-depth algorithmic complexity results.