<p>The answer to both questions is yes.</p>
<p>The standard reduction from 3-SAT to 3DM – as used by Garey and Johnson, for example – is not parsimonious, but there is a sequence of parsimonious reductions that goes:</p>
<p>3-SAT → 1-IN-3-SAT → MONOTONE-1-IN-3-SAT → 3DM</p>
<p>Moreover, these reductions can be done in a way that preserves planarity. The details can be found in [1, 2]. The key reduction MONOTONE-1-IN-3-SAT → 3DM is from [1]. It is shown to be parsimonious by [2], which also shows how to do the other reductions in a parsimonious way. The reduction from 3-SAT to PLANAR-3-SAT is done using the crossover gadget from [3], which [2] also shows to be parsimonious.</p>
<p>[1] M.E Dyer, A.M Frieze, <em>Planar 3DM is NP-complete</em>, Journal of Algorithms, Volume 7, Issue 2 (June 1986), Pages 174-184. <a href="http://www.math.cmu.edu/%7Eaf1p/Texfiles/PLANAR3DM.pdf" rel="nofollow noreferrer">PDF</a></p>
<p>[2] Harry B. Hunt, III, Madhav V. Marathe, Venkatesh Radhakrishnan, and Richard E. Stearns. <em>The Complexity of Planar Counting Problems</em>. SIAM J. Comput. 27, 4 (August 1998), 1142-1167. <a href="http://arxiv.org/abs/cs/9809017" rel="nofollow noreferrer">arXiv:cs/9809017</a></p>
<p>[3] David Lichtenstein. <em>Planar Formulae and Their Uses</em>, SIAM Journal on Computing 11:2 (1982), 329-343. <a href="http://dx.doi.org/10.1137/0211025" rel="nofollow noreferrer">doi:10.1137/0211025</a></p>

CC BY-SA 4.0
2021-04-26T05:44:16.027Z
[This](http://dx.doi.org/10.1137/0211025) is a working link to [3] (unfortunately, pdf is under a paywall).
Cyriac Antony
CC BY-SA 4.0
2021-04-26T10:37:41.673Z
@CyriacAntony Oh! Thank you for pointing out that the link I used no longer works. [This](https://www.math.ucdavis.edu/~deloera/MISC/LA-BIBLIO/trunk/Lichtenstein/Lichtenstein1.pdf) link is not paywalled, but it’s a hard-to-read scan of an nth-generation photocopy.
Robin Houston
CC BY-SA 4.0
2014-08-13T11:03:44.930Z
2021-04-26T10:39:16.093Z
2021-04-26T10:39:16.093Z
Robin Houston
<p>Let UNAMBIGUOUS-3DM be defined by analogy to UNAMBIGUOUS-SAT, i.e. as a promise problem version of three-dimensional matching where we may assume there is no more than one solution.</p>
<ol>
<li><p>Is there a randomised reduction from SAT, as there is for UNAMBIGUOUS-SAT, so that a polynomial-time algorithm for UNAMBIGUOUS-3DM would imply NP=RP?</p>
<p>For example, it would suffice for there to be a parsimonious reduction from SAT to 3DM, but I haven't found one in the literature.</p>
</li>
<li><p>If so, does it still work when restricting to planar instances of 3DM, i.e. where the bipartite graph associated with the 3DM instance is planar?</p>
</li>
</ol>

<cc.complexity-theory><reference-request>
Hardness of UNAMBIGUOUS-3DM
Robin Houston
# Hardness of UNAMBIGUOUS-3DM

(Asked by: username_0 on 2014-07-22)

Let UNAMBIGUOUS-3DM be defined by analogy to UNAMBIGUOUS-SAT, i.e. as a promise problem version of three-dimensional matching where we may assume there is no more than one solution.

1. Is there a randomised reduction from SAT, as there is for UNAMBIGUOUS-SAT, so that a polynomial-time algorithm for UNAMBIGUOUS-3DM would imply NP=RP?

   For example, it would suffice for there to be a parsimonious reduction from SAT to 3DM, but I haven't found one in the literature.
2. If so, does it still work when restricting to planar instances of 3DM, i.e. where the bipartite graph associated with the 3DM instance is planar?

**Tags:** cc.complexity-theory, reference-request

---

## 1 answers

### Answer by username_0 on 2014-08-13. Score: 7 | Accepted answer

The answer to both questions is yes.

The standard reduction from 3-SAT to 3DM – as used by Garey and Johnson, for example – is not parsimonious, but there is a sequence of parsimonious reductions that goes:

3-SAT → 1-IN-3-SAT → MONOTONE-1-IN-3-SAT → 3DM

Moreover, these reductions can be done in a way that preserves planarity. The details can be found in [1, 2]. The key reduction MONOTONE-1-IN-3-SAT → 3DM is from [1]. It is shown to be parsimonious by [2], which also shows how to do the other reductions in a parsimonious way. The reduction from 3-SAT to PLANAR-3-SAT is done using the crossover gadget from [3], which [2] also shows to be parsimonious.

[1] M.E Dyer, A.M Frieze, *Planar 3DM is NP-complete*, Journal of Algorithms, Volume 7, Issue 2 (June 1986), Pages 174-184. [PDF](http://www.math.cmu.edu/%7Eaf1p/Texfiles/PLANAR3DM.pdf)

[2] Harry B. Hunt, III, Madhav V. Marathe, Venkatesh Radhakrishnan, and Richard E. Stearns. *The Complexity of Planar Counting Problems*. SIAM J. Comput. 27, 4 (August 1998), 1142-1167. [arXiv:cs/9809017](http://arxiv.org/abs/cs/9809017)

[3] David Lichtenstein. *Planar Formulae and Their Uses*, SIAM Journal on Computing 11:2 (1982), 329-343. [doi:10.1137/0211025](http://dx.doi.org/10.1137/0211025)

> **Comments:**
> **username_1**: [This](http://dx.doi.org/10.1137/0211025) is a working link to [3] (unfortunately, pdf is under a paywall).  
> **username_0**: @CyriacAntony Oh! Thank you for pointing out that the link I used no longer works. [This](https://www.math.ucdavis.edu/~deloera/MISC/LA-BIBLIO/trunk/Lichtenstein/Lichtenstein1.pdf) link is not paywalled, but it’s a hard-to-read scan of an nth-generation photocopy.  

---

