2018/08/29 by Manuel Bodirsky, Bodirsky, Manuel, Marcello Mamino +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1808.10068
openalex publication_date 2018/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A subset of Qn is called semilinear (or piecewise linear) if it is Boolean combination of linear half-spaces. We study the computational complexity of the constraint satisfaction problem (CSP) over the rationals when all the constraints are semilinear. When the sets are convex the CSP is polynomial-time equivalent to linear programming. A semilinear relation is convex if and only if it is preserved by taking averages. Our main result is a polynomial-time algorithm for the CSP of semilinear constraints that are preserved by applying medians. We also prove that this class is maximally tractable in the sense that any larger class of semilinear relations has an NP-hard CSP. To illustrate, our class contains all relations that can be expressed by linear inequalities with at most two variables (so-called TVPI constraints), but it also contains many non-convex relations, for example constraints of the form x in S for arbitrary finite subset S of Q, or more generally disjunctive constraints of the form x < c or y < d for constants c and d.