2 papers
cs.CC2026
The Complexity of Boolean Connectivity Problem of -Horn Formulas
Takashi Horiyama, Shoon Mineyoshi, Yuto Okura +2
The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the -dimensional hypercube. This problem…
cs.CC2026
Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
Kosuke Susukita, Junichi Teruyama
Proving the NP-completeness of pencil-and-paper puzzles typically relies on reductions from combinatorial problems such as the satisfiability problem (SAT). Although the properties…