Counting Exact-One Hitting Sets in Subexponential TimeResearch Paper
Exact-One Hitting Set asks for a set of elements that meets every member of a given family exactly once. It is one of Karp's 21 NP-complete problems (Karp 1972, Problem 15), and in the language of satisfiability it is monotone exact satisfiability (XSAT): every set imposes the constraint "exactly one of these variables is true". Positive one-in-three…