HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

NP-hard $k$-SAT variant with exactly $\ell$ occurrences per variable

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
satvariablevariantoccurrencesperwithhardellexactly

Problem

For the purpose of this post, let $k$-SAT be SAT with exactly $k$ literals per clause, as opposed to the more common meaning of at most $k$ literals per clause.

With the purpose of proving some problem NP-hard, I'd like to reduce from a $k$-SAT variant (which of course should remain NP-hard) in which each variable occurs exactly $\ell$ times in the formula.

I've tried to look up 3-SAT with exactly 3 occurrences of a variable, but this paper proves 3-SAT with at most 3 occurrences per variable is trivial, which includes my specific case of exactly 3 occurrences. (In fact, this is the case whenever $k = \ell$.)

All hope is not lost though, as in the same paper, it is proven that 3-SAT with at most $\ell$
occurrences per variable, with $\ell>3$ is NP-hard. I'm looking into the details of the reduction to see if by chance they have proved the specific case of exactly $\ell$ occurrences per variable to be NP-hard (which would extend to the general case of at most $\ell$ occurrences per variable), but wanted to ask this question here while searching:

Does there exist an NP-hard $k$-SAT variant with exactly $\ell$ occurrences per variable?

Solution

The problem of deciding the satisfiability of 3CNFs in which each variable occurs exactly 5 times is NP-complete (and even NP-hard to approximate), see Uriel Feige, A threshold of $\ln n$ for approximating Set Cover.

Context

StackExchange Computer Science Q#154812, answer score: 3

Revisions (0)

No revisions yet.