6
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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

[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

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

$\endgroup$
2
  • $\begingroup$ This is a working link to [3] (unfortunately, pdf is under a paywall). $\endgroup$ Apr 26 at 5:44
  • $\begingroup$ @CyriacAntony Oh! Thank you for pointing out that the link I used no longer works. This link is not paywalled, but it’s a hard-to-read scan of an nth-generation photocopy. $\endgroup$ Apr 26 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.