Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
A Parametric Polynomial Deterministic Algorithm for #2SAT
verfasst von : J. Raymundo Marcial-Romero, Guillermo De Ita Luna, J. Antonio Hernández, Rosa María Valdovinos
Erschienen in: Advances in Artificial Intelligence and Soft Computing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Counting models for two Conjunctive Normal Form formulae (2-CFs), known as the #2SAT problem, is a classic #P complete problem. It is known that if the constraint graph of a 2-CF F is acyclic or contains loops and parallel edges, \(\#2SAT(F)\) can be computed efficiently. In this paper we address the cyclic case different from loops and parallel edges.
If the constraint graph G of a 2-CF F is cyclic, T a spanning tree plus loops and parallel edges of G and \(\overline{T}=G\setminus T\), what we called its cotree, we show that by building a set partition \(\cup T_i\) of \(\overline{T}\), where each \(T_i\) of the partition is formed by the frond edges of the cycles that are chained via other intersected cycles, then a parametric polynomial deterministic procedure for computing #2SAT with time complexity for the worst case of \(O(2^{k} \cdot poly(|E(T)|))\) can be obtained, where poly is a polynomial function, and k is the cardinality of the largest set in the partition.
This method shows that #2SAT is in the class of fixed-parameter tratable (FPT) problems, where the fixed-parameter k in our proposal, depends on the number of edges of a subcotree of a decomposition of the constraint graph (tree+loops+parallel:cotree) associated to the formula.