Linear satisfiability preserving assignments

Kei Kimura, Kazuhisa Makino

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


In this paper, we study several classes of satisfiability preserving assignments to the con- straint satisfaction problem (CSP). In particular, we consider fixable, autark and satisfying assignments. Since it is in general NP-hard to find a nontrivial (i.e., nonempty) satisfiability preserving assignment, we introduce linear satisfiability preserving assignments, which are defined by polyhedral cones in an associated vector space. The vector space is obtained by the identification, introduced by Kullmann, of assignments with real vectors. We consider arbitrary polyhedral cones, where only restricted classes of cones for autark assignments are considered in the literature. We reveal that cones in certain classes are maximal as a convex subset of the set of the associated vectors, which can be regarded as extensions of Kullmann's results for autark assignments of CNFs. As algorithmic results, we present a pseudo-polynomial time algorithm that computes a linear fixable assignment for a given in- teger linear system, which implies the well known pseudo-polynomial solvability for integer linear systems such as two-variable-per-inequality (TVPI), Horn and q-Horn systems.

Original languageEnglish
Pages (from-to)291-321
Number of pages31
JournalJournal of Artificial Intelligence Research
Publication statusPublished - Feb 1 2018
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence


Dive into the research topics of 'Linear satisfiability preserving assignments'. Together they form a unique fingerprint.

Cite this