One-in-Two-Matching Problem is NP-complete
| dc.creator | Caracciolo, Sergio | |
| dc.creator | Fichera, Davide | |
| dc.creator | Sportiello, Andrea | |
| dc.date | 2006-04-28 | |
| dc.date.accessioned | 2026-07-07T07:09:26Z | |
| dc.date.available | 2026-07-07T07:09:26Z | |
| dc.description | 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 \leq 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. | |
| dc.description | 30 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0604113 | |
| dc.identifier | http://arxiv.org/abs/cs/0604113 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/111063 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.2.2 | |
| dc.title | One-in-Two-Matching Problem is NP-complete | |
| dc.type | text |