2006/04/28 by Sergio Caracciolo, Caracciolo, Sergio, Davide Fichera +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #DNA and Biological Computing #F.2.2 #FOS: Computer and information sciences #Optimization and Search Problems #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0604113
30 pages
arxiv created 2006/04/28 · openalex publication_date 2006/04/28 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
2-dimensional Matching Problem, which requires to find a matching of left- to right-vertices in a balanced 2n-vertex bipartite graph, is a well-known polynomial problem, while various variants, like the 3-dimensional analogoue (3DM, with triangles on a tripartite graph), or the Hamiltonian Circuit Problem (HC, a restriction to ``unicyclic'' matchings) are among the main examples of NP-hard problems, since the first Karp reduction series of 1972. The same holds for the weighted variants of these problems, the Linear Assignment Problem being polynomial, and the Numerical 3-Dimensional Matching and Travelling Salesman Problem being NP-complete. In this paper we show that a small modification of the 2-dimensional Matching and Assignment Problems in which for each i ≤ n/2 it is required that either π(2i-1)=2i-1 or π(2i)=2i, is a NP-complete problem. The proof is by linear reduction from SAT (or NAE-SAT), with the size n of the Matching Problem being four times the number of edges in the factor graph representation of the boolean problem. As a corollary, in combination with the simple linear reduction of One-in-Two Matching to 3-Dimensional Matching, we show that SAT can be linearly reduced to 3DM, while the original Karp reduction was only cubic.