2026-08-10T23:43:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25157 2026-02-09T08:17:59Z ddc:004 open_access

Exact Algorithms and Hardness Result for the Boolean Connectivity Problem of k-Horn Formulas Horiyama, Takashi Okura, Yuto Seto, Kazuhisa Teruyama, Junichi k-Horn Boolean connectivity bounded variable occurrence hardness exact algorithm satisfiability The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the n-dimensional hypercube. This problem is known to be coNP-complete, even when restricted to k-Horn formulas for k ≥ 3, as shown by Makino, Tamaki, and Yamamoto. In this paper, we further investigate the complexity of the Boolean connectivity problem for k-Horn formulas, referred to as Conn k-Horn. We first present an exact exponential-time algorithm for Conn k-Horn without any structural restrictions. Our algorithm builds on the deterministic PPZ algorithm proposed by Paturi, Pudlák, and Zane. It runs in O^*(2^{(1-1/2k)n}) time, achieving an exponential improvement over the previously known algorithm for the Boolean connectivity problem of k-CNF formulas, shown by Makino, Tamaki, and Yamamoto. We then examine both algorithmic and hardness results for Conn 3-Horn under bounded variable occurrences. On the algorithmic side, we propose a polynomial-time algorithm for Conn 3-Horn when each clause contains exactly three literals and each variable appears at most three times. This result generalizes to Conn k-Horn under the same structural constraints, in which each clause contains exactly k literals and each variable appears at most k times. On the hardness side, we prove that Conn 3-Horn remains coNP-complete even when restricted to instances in which each variable appears exactly four times. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Takashi Horiyama and Yuto Okura and Kazuhisa Seto and Junichi Teruyama 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.25 urn:nbn:de:0030-drops-251577 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.25 eng https://creativecommons.org/licenses/by/4.0/legalcode