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 par...
详细信息
ISBN:
(纸本)9783319270609;9783319270593
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 (T) over bar = G \ T, what we called its cotree, we show that by building a set partition boolean OR T-i of (T) over bar, 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) . 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.
暂无评论