On the Maximum Edge-Pair Embedding Bipartite Matching

Given a set of edge pairs in a bipartite graph, we want to find a bipartite matching that includes a maximum number of those edge pairs. While the problem has many applications to wireless localization, to the best of our knowledge, there is no theoretical work for the problem. In this work, unless \(P = NP\), we show that there is no constant approximation for the problem. Suppose that k denotes the maximum number of input edge pairs such that a particular node can be in. Inspired by experimental results, we consider the case that k is small. While there is a simple polynomial-time algorithm for the problem when k is one, we show that the problem is NP-hard when k is greater than one. We also devise an efficient O(k)-approximation algorithm for the problem.