Abstract of Paper

Generalized satisfiability with \( k \) occurrences per variable: A - Study through Delta-matroid Parity
by Victor Dalmau and Daniel Ford

Abstract:

In this paper we examine generalized satisfiability problems with
variable occurrences. First, we show that \( 3 \) occurrences per
variable suffice to make these problems as hard as their unrestricted
version. Then we focus on generalized satisfiability problems with at
most \( 2 \) occurrences per variable. It is known that some \( NP
\)-complete generalized satisfiability problems become polynomially
solvable when only \( 2 \) occurrences per variable are allowed. We
identify two new families of generalized satisfiability problems,
called local and binary, that are polynomially solvable when only \( 2
\) occurrences per variable are allowed. We achieve this result by
means of a reduction to the \( \Delta \)-Matroid Parity Problem, which
is another important theme of this work.