Paper Info
Title
Max-Closed Semilinear Constraint Satisfaction
Abstract
A semilinear relation $$S \\subseteq {\\mathbb Q}^n$$ is max-closed if it is preserved by taking the componentwise maximum. The constraint satisfaction problem for max-closed semilinear constraints is at least as hard as determining the winner in Mean Payoff Games, a notorious problem of open computational complexity. Mean Payoff Games are known to be inï¾ź$$\\mathsf {NP}\\cap \\mathsf {co}\\text {-}\\mathsf {NP}$$, which is not known for max-closed semilinear constraints. Semilinear relations that are max-closed and additionally closed under translations have been called tropically convex in the literature. One of our main results is a new duality for open tropically convex relations, which puts the CSP for tropically convex semilinear constraints in general intoï¾ź$$\\mathsf {NP}\\cap \\mathsf {co}\\text {-}\\mathsf {NP}$$. This extends the corresponding complexity result for scheduling under and-or precedence constraints, or equivalently the max-atoms problem. To this end, we present a characterization of max-closed semilinear relations in terms of syntactically restricted first-order logic, and another characterization in terms of a finite set of relations L that allow primitive positive definitions of all other relations in the class. We also present a subclass of max-closed constraints where the CSP is in $$\\mathsf {P}$$; this class generalizes the class of max-closed constraints over finite domains, and the feasibility problem for max-closed linear inequalities. Finally, we show that the class of max-closed semilinear constraints is maximal in the sense that as soon as a single relation that is not max-closed is added toï¾źL, the CSP becomes $$\\mathsf {NP}$$-hard.
Year
DOI
Venue
2015
10.1007/978-3-319-34171-2_7
CSR
DocType
Volume
ISSN
Journal
abs/1506.04184
0302-9743
Citations 
PageRank 
References 
0
0.34
10
Authors
2
Name
Order
Citations
PageRank
Manuel Bodirsky164454.63
Marcello Mamino2165.51