2026-09-17T02:11:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24250 2026-09-05T18:39:56Z ddc:004 open_access

On the Enumeration of Signatures of XOR-CNF’s Creignou, Nadia Defrain, Oscar Olive, Frédéric Vilmin, Simon Algorithmic enumeration XOR-CNF signatures maximal bipartite subgraphs enumeration extension proximity search Given a CNF formula φ with clauses C_1, … , C_m over a set of variables V, a truth assignment 𝐚: V → {0, 1} generates a binary sequence σ_φ(𝐚) = (C_1(𝐚), …, C_m(𝐚)), called a signature of φ, where C_i(𝐚) = 1 if clause C_i evaluates to 1 under assignment 𝐚, and C_i(𝐚) = 0 otherwise. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration. In a recent paper, Bérczi et al. interestingly proved that generating signatures of a CNF is tractable despite the fact that verifying a solution is hard. They also showed the hardness of finding maximal signatures of an arbitrary CNF due to the intractability of satisfiability in general. Their contribution leaves open the problem of efficiently generating maximal signatures for tractable classes of CNFs, i.e., those for which satisfiability can be solved in polynomial time. Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNF’s. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nadia Creignou and Oscar Defrain and Frédéric Olive and Simon Vilmin 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.19 urn:nbn:de:0030-drops-242508 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.19 eng https://creativecommons.org/licenses/by/4.0/legalcode