A Note on the Use of Independent Sets for the k -SAT Problem

Abstract

An independent set of variables is one in which no two variables occur in the same clause in a given k-SAT instance. Recently, independent sets have obtained more attention. Due to a simple observation we prove that a k-SAT instance over n variables with independent set of size i can be solved in time $\mathcal{O}\mathrm{(}{\mathit{\varphi }}_{2\mathrm{(}\mathit{k}-1\mathrm{)}}\mathrm{(}\mathit{n}-\mathit{i}\mathrm{)}\mathrm{)}$ where ${\mathit{\varphi }}_{\mathit{k}}\mathrm{(}\mathit{n}\mathrm{)}$ denotes an upper bound on the complexity of solving k-SAT over n variables.