A bottom-up algorithm for solving ♯2SAT

Logic Journal of the IGPL 28 (6):1130-1140 (2020)
  Copy   BIBTEX

Abstract

Counting models for a two conjunctive formula $F$, a problem known as $\sharp $2Sat, is a classic $\sharp $P complete problem. Given a 2-CF $F$ as input, its constraint graph $G$ is built. If $G$ is acyclic, then $\sharp $2Sat can be computed efficiently. In this paper, we address the case when $G$ has cycles. When $G$ is cyclic, we propose a decomposition on the constraint graph $G$ that allows the computation of $\sharp $2Sat in incremental way. Let $T$ be a cactus graph of $G$ containing a maximal number of independent cycles, and let $\overline{T}=-E)$ be a subset of frond edges from $G$. The clauses in $\overline{T}$ are ordered in connected components $\{K_1, \ldots, K_r\}$. Each $, i=1,\ldots,r$ is a knot of the graph. The arrangement of the clauses of $\overline{T}$ allows the decomposition of $G$ in knots and provides a way of computing $\sharp $2Sat in an incremental way. Our procedure has a bottom-up orientation for the computation of $\sharp $2Sat. It begins with $F_0 = T$. In each iteration of the procedure, a new clause $C_i \in \overline{T}$ is considered in order to form $F_i = $ and then to compute $\sharp $2Sat$$ based on the computation of $\sharp $2Sat$$.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,098

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

An undecidability theorem for lattices over group rings.Carlo Toffalori - 1997 - Annals of Pure and Applied Logic 88 (2-3):241-262.
Twilight graphs.J. C. E. Dekker - 1981 - Journal of Symbolic Logic 46 (3):539-571.
Partitions of large Rado graphs.M. Džamonja, J. A. Larson & W. J. Mitchell - 2009 - Archive for Mathematical Logic 48 (6):579-606.
A Note on Triple Repetition Sequence of Domination Number in Graphs.Leomarich Casinillo, Emily Casinillo & Lanndon Ocampo - 2022 - Inprime: Indonesian Journal of Pure and Applied Mathematics 4 (2):72-81.
Conjugacy for homogeneous ordered graphs.Samuel Coskey & Paul Ellis - 2019 - Archive for Mathematical Logic 58 (3-4):457-467.
Sur la transformation d'Abel-Radon des courants localement résiduels.Bruno Fabre - 2005 - Annali della Scuola Normale Superiore di Pisa- Classe di Scienze 4 (1):27-57.

Analytics

Added to PP
2020-05-06

Downloads
15 (#976,359)

6 months
9 (#355,374)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Jimmy Hernandez
Universidad Pontificia de Salamanca
Jordi Romero
Universitat Oberta de Catalunya

Citations of this work

No citations found.

Add more citations

References found in this work

On the hardness of approximate reasoning.Dan Roth - 1996 - Artificial Intelligence 82 (1-2):273-302.

Add more references