Exact enumeration of satisfiable 2-SAT formulae

DOI10.5070/C63261985arXiv2108.08067OpenAlexW3194217435MaRDI QIDQ6138912FDOQ6138912

Authors: Sergey Dovgal, Elie de Panafieu, Vlady Ravelomanana 

Publication date: 16 December 2023

Published in: Combinatorial Theory (Search for Journal in Brave)

Abstract: We obtain exact expressions counting the satisfiable 2-SAT formulae and describe the structure of associated implication digraphs. Our approach is based on generating function manipulations. To reflect the combinatorial specificities of the implication digraphs, we introduce a new kind of generating function, the Implication generating function, inspired by the Graphic generating function used in digraph enumeration. Using the underlying recurrences, we make accurate numerical predictions of the phase transition curve of the 2-SAT problem inside the critical window. We expect these exact formulae to be amenable to rigorous asymptotic analysis using complex analytic tools, leading to a more detailed picture of the 2-SAT phase transition in the future.

Full work available at URL: https://arxiv.org/abs/2108.08067

zbMATH Keywords

generating functionsphase transitionsexact enumerationrandom graphssatisfiabilitystrongly connected components2-CNF

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Exact enumeration problems, generating functions (05A15)

Cites Work

• Analytic combinatorics
• Title not available (Why is that?)
• The number of connected sparsely edged graphs
• Title not available (Why is that?)
• The birth of the giant component
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Paths in graphs
• Some optimal inapproximability results
• The complexity of theorem-proving procedures
• Title not available (Why is that?)
• Some simplified NP-complete graph problems
• The probabilistic method
• Title not available (Why is that?)
• Title not available (Why is that?)
• Enumerative applications of a decomposition for graphs and digraphs
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
• Une théorie combinatoire des séries formelles
• The continuum limit of critical random graphs
• The transitive closure of a random digraph
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Asymptotic Expansion for the Coefficients of Some Formal Power Series
• The Number of Strong Digraphs
• The scaling window of the 2-SAT transition
• Random 2-SAT: Results and problems
• A threshold for unsatisfiability
• Counting directed acyclic and elementary digraphs
• Random MAX SAT, random MAX CUT, and their phase transitions
• The critical behavior of random digraphs
• The phase transition in the evolution of random digraphs
• Random 2 XORSAT phase transition
• Airy phenomena and analytic combinatorics of connected graphs
• How frequently is a system of 2-linear Boolean equations solvable?
• The asymptotic \(k\)-SAT threshold
• On Some Features of the Structure of a Random Graph Near a Critical Point
• Phase transition of random non-uniform hypergraphs
• Proof of the satisfiability conjecture for large \(k\)
• Threshold functions for small subgraphs in simple graphs and multigraphs
• Analytic combinatorics of connected graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (1)

• An enumerative algorithm for \#2SAT

This page was built for publication: Exact enumeration of satisfiable 2-SAT formulae

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6138912)