MATHEMATICAL ENGINEERING TECHNICAL REPORTS Satisability Preserving Assignments and Their Local and Linear Forms
Kei Kimura, Kazuhisa Makino · 2014
In this paper, we study several variable-based satisfiability preserving assignments to the constraint satisfaction problem. In particular, we consider fixable, autark and satisfiable partial assignments, as well as their local and linear forms. We show the inclusion relationships among the original and local forms of the satisfiability preserving assignments, and discuss maximality for linear satisfiability preserving assignments, which are defined as linear cones of the associated real space. As an application, we present a pseudo-polynomial time algorithm that computes a linear fixable assignment for integer linear systems, which also implies the well known pseudo-polynomially for integer linear systems such as two variables par inequality (TVPI), Horn and q-Horn systems.