Dalmau, Victor; Ford, Daniel K. Generalized satisfiability with limited occurrences per variable: A study through delta-matroid parity. (English) Zbl 1124.68372 Rovan, Branislav (ed.) et al., Mathematical foundations of computer science 2003. 28th international symposium, MFCS 2003, Bratislava, Slovakia, August 25–29, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40671-9/pbk). Lect. Notes Comput. Sci. 2747, 358-367 (2003). Summary: In this paper we examine generalized satisfiability problems with limited 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 \(\triangle\)-matroid parity problem, which is another important theme of this work.For the entire collection see [Zbl 1025.00004]. Cited in 12 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) PDFBibTeX XMLCite \textit{V. Dalmau} and \textit{D. K. Ford}, Lect. Notes Comput. Sci. 2747, 358--367 (2003; Zbl 1124.68372) Full Text: DOI