@techreport{oai:ipsj.ixsq.nii.ac.jp:00241900,
 author = {Yuto, Okura and Junichi, Teruyama and Kazuhisa, Seto and Takashi, Horiyama and Yuto, Okura and Junichi, Teruyama and Kazuhisa, Seto and Takashi, Horiyama},
 issue = {12},
 month = {Jan},
 note = {The Boolean connectivity problem asks whether the satisfying assignments of a given Boolean formula are connected over the n-dimensional hypercube. Makino, Yamamoto, and Tamaki showed that this problem is coNP-complete even if a given formula is restricted to a 3-Horn formula. In this paper, we show that the deterministic PPZ algorithm presented by Paturi, Pudlak, and Zane can solve the Boolean Connectivity of a given k-Horn formula over n variables in time O*(2(1-1/2k)n). It can also count the number of the connected components of satisfying assignments., The Boolean connectivity problem asks whether the satisfying assignments of a given Boolean formula are connected over the n-dimensional hypercube. Makino, Yamamoto, and Tamaki showed that this problem is coNP-complete even if a given formula is restricted to a 3-Horn formula. In this paper, we show that the deterministic PPZ algorithm presented by Paturi, Pudlak, and Zane can solve the Boolean Connectivity of a given k-Horn formula over n variables in time O*(2(1-1/2k)n). It can also count the number of the connected components of satisfying assignments.},
 title = {Exact Algorithm for the Boolean Connectivity of <i>k</i>-Horn Formulas via Deterministic PPZ},
 year = {2025}
}