TY - JOUR

T1 - Linear satisfiability preserving assignments

AU - Kimura, Kei

AU - Makino, Kazuhisa

N1 - Publisher Copyright:
© 2018 AI Access Foundation.

PY - 2018/2/1

Y1 - 2018/2/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85044149390&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85044149390&partnerID=8YFLogxK

U2 - 10.1613/jair.5658

DO - 10.1613/jair.5658

M3 - Article

AN - SCOPUS:85044149390

SN - 1076-9757

VL - 61

SP - 291

EP - 321

JO - Journal of Artificial Intelligence Research

JF - Journal of Artificial Intelligence Research

ER -