The Algorithmic Complexity of the Paired Matching Problem

We introduce a new matching problem originating from industry called the Paired Matching problem. The objective in the problem is to find a maximum matching of minimum cost in a bipartite graph. This is complicated by a non-trivial definition of cost, which is expressed based on a pairing of the vertices in one partite set. We prove that the problem is NP-complete even under further restrictions. We also study the parameterized complexity of the problem and give an exact algorithm for it using kernelization. In doing so, we show that the problem can be solved efficiently even on large inputs, as long as a given one of the partite sets is small.