Paper Info
Title
On the Boolean Connectivity Problem for Horn Relations
Abstract
Gopalan et al. studied in ICALP06 [17] connectivity properties of the solution-space of Boolean formulas, and investigated complexity issues on the connectivity problems in Schaefer’s framework. A set S of logical relations is Schaefer if all relations in S are either bijunctive, Horn, dual Horn, or affine. They conjectured that the connectivity problem for Schaefer is in P\mathcal{P} . We disprove their conjecture by showing that there exists a set S of Horn relations such that the connectivity problem for S is co NP\mathcal{NP} -complete. We also show that the connectivity problem for bijunctive relations can be solved in O( min {n|ϕ|, T(n)}) time, where n denotes the number of variables, ϕ denotes the corresponding 2-CNF formula, and T(n) denotes the time needed to compute the transitive closure of a directed graph of n vertices. Furthermore, we investigate a tractable aspect of Horn and dual Horn relations with respect to characteristic sets.
Year
DOI
Venue
2010
10.1007/978-3-540-72788-0_20
Discrete Applied Mathematics
Keywords
Field
DocType
directed graph,boolean satisfiability,transitive closure
Discrete mathematics,Combinatorics,Vertex (geometry),Existential quantification,Directed graph,Disjunctive normal form,Constraint satisfaction problem,Transitive closure,True quantified Boolean formula,Conjecture,Mathematics
Journal
Volume
Issue
ISSN
158
18
0302-9743
Citations 
PageRank 
References 
7
0.65
29
Authors
3
Name
Order
Citations
PageRank
Kazuhisa Makino11088102.74
Suguru Tamaki28712.84
Masaki Yamamoto370.65