Enumerating induced s-t hyperpaths and minimal s-t separators in directed hypergraphs is not output-polynomial unless P=NP, and s-t hyperpath enumeration on BF-hypergraphs is at least as hard as the 45-year-old minimal transversal enumeration problem.
On the enumeration of signatures of XOR-CNF's
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
Given a CNF formula $\varphi$ with clauses $C_1, \dots, C_m$ over a set of variables $V$, a truth assignment $\mathbf{a} : V \to \{0, 1\}$ generates a binary sequence $\sigma_\varphi(\mathbf{a})=(C_1(\mathbf{a}), \ldots, C_m(\mathbf{a}))$, called a signature of $\varphi$, where $C_i(\mathbf{a})=1$ if clause $C_i$ evaluates to 1 under assignment $\mathbf{a}$, and $C_i(\mathbf{a})=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\'erczi 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-CNFs.
fields
cs.DS 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
Enumerating induced s-t hyperpaths and minimal s-t separators in directed hypergraphs is not output-polynomial unless P=NP, and s-t hyperpath enumeration on BF-hypergraphs is at least as hard as the 45-year-old minimal transversal enumeration problem.