16
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      From Hall's Marriage Theorem to Boolean Satisfiability and Back

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Motivated by the application of Hall's Marriage Theorem in various LP-rounding problems, we introduce a generalization of the classical marriage problem (CMP) that we call the Fractional Marriage Problem. We show that the Fractional Marriage Problem is NP-Complete by reduction from Boolean Satisfiability (SAT). We show that when we view the classical marriage problem (a.k.a. bipartite matching) as a sub-class of SAT we get a new class of polynomial-time satisfiable SAT instances that we call CMP-SAT, different from the classically known polynomial-time satisfiable SAT instances 2-SAT, Horn-SAT and XOR-SAT. We next turn to the problem of recognizing CMP-SAT instances, first using SAT embeddings, and then using their embeddings within the universe of Fractional Marriage Problems (FMPs). In the process we are led to another generalization of the CMP that we call the Symmetric Marriage Problem, which is polynomial time decidable and leads to a slight enlargement of the CMP-SAT class. We develop a framework for simplifying FMP problems to identify CMP instances that we call Fragment Logic. Finally we give a result that sheds light on how expressive the FMP need be to still be NP-Complete. The result gives a second NP-Complete reduction of the FMP, this time to Tripartite Matching. We conclude with a wide assortment of suggested additional problems.

          Related collections

          Most cited references5

          • Record: found
          • Abstract: not found
          • Article: not found

          Linear-time algorithms for testing the satisfiability of propositional horn formulae

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Centrality of trees for capacitated \(k\) k -center

              Bookmark
              • Record: found
              • Abstract: not found
              • Conference Proceedings: not found

              LP Rounding for k-Centers with Non-uniform Hard Capacities

                Bookmark

                Author and article information

                Journal
                15 April 2019
                Article
                1904.07218
                224983c0-67b2-4190-a1c5-19e6198eeadf

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                cs.CC math.CO

                Combinatorics,Theoretical computer science
                Combinatorics, Theoretical computer science

                Comments

                Comment on this article