More Web Proxy on the site http://driver.im/

research-article

Distance constraint satisfaction problems

Authors:

Manuel Bodirsky,

Barnaby Martin,

Antoine Mottet,

Michael PinskerAuthors Info & Claims

Information and Computation, Volume 247, Issue C

Pages 87 - 105

https://doi.org/10.1016/j.ic.2015.11.010

Published: 01 April 2016 Publication History

Abstract

We study the complexity of constraint satisfaction problems for templates over the integers where the relations are first-order definable from the successor function. In the case that is locally finite (i.e., the Gaifman graph of has finite degree), we show that is homomorphically equivalent to a structure with one of two classes of polymorphisms (which we call modular max and modular min) and the CSP for can be solved in polynomial time, or is homomorphically equivalent to a finite transitive structure, or the CSP for is NP-complete. Assuming a widely believed conjecture from finite domain constraint satisfaction (we require the tractability conjecture by Bulatov, Jeavons and Krokhin in the special case of transitive finite templates), this proves that those CSPs have a complexity dichotomy, that is, are either in P or NP-complete.

References

[1]

Libor Barto, Marcin Kozik, New conditions for Taylor varieties and CSP, in: Proceedings of LICS, 2010, pp. 100-109.

[2]

Manuel Bodirsky, Cores of countably categorical structures, Log. Methods Comput. Sci., 3 (2007) 1-16.

[3]

Manuel Bodirsky, Hubie Chen, Michael Pinsker, The reducts of equality up to primitive positive interdefinability, J. Symb. Log., 75 (2010) 1249-1292.

[4]

Manuel Bodirsky, Víctor Dalmau, Barnaby Martin, Michael Pinsker, Distance constraint satisfaction problems, in: Lecture Notes in Computer Science, Springer Verlag, August 2010, pp. 162-173.

[5]

Manuel Bodirsky, Martin Grohe, Non-dichotomies in constraint satisfaction complexity, in: Lecture Notes in Computer Science, Springer Verlag, July 2008, pp. 184-196.

[6]

Manuel Bodirsky, Martin Hils, Barnaby Martin, On the scope of the universal-algebraic approach to constraint satisfaction, in: Proceedings of the Annual Symposium on Logic in Computer Science, IEEE Computer Society, July 2010, pp. 90-99.

[7]

Manuel Bodirsky, Jan Kára, The complexity of temporal constraint satisfaction problems, J. ACM, 57 (2009) 1-41.

Digital Library

[8]

Manuel Bodirsky, Dugald Macpherson, Johan Thapper, Constraint satisfaction tractability from semi-lattice operations on infinite sets, ACM Trans. Comput. Log., 14 (2013) 1-30.

Digital Library

[9]

Manuel Bodirsky, Antoine Mottet, Barnaby Martin, Constraint satisfaction problems over the integers with successor, in: Proceedings of ICALP, 2015. arXiv:1503.08572

[10]

Manuel Bodirsky, Jaroslav Nešetřil, Constraint satisfaction with countable homogeneous templates, J. Log. Comput., 16 (2006) 359-373.

[11]

Manuel Bodirsky, Michael Pinsker, Schaefer's theorem for graphs, J. ACM, 62 (2015).

[12]

A. Bulatov, M. Valeriote, Results on the algebraic approach to the csp, in: Complexity of Constraints: An Overview of Current Research Themes, Springer Verlag, 2008, pp. 68-92.

[13]

Andrei A. Bulatov, Andrei A. Krokhin, Peter G. Jeavons, Classifying the complexity of constraints using finite algebras, SIAM J. Comput., 34 (2005) 720-742.

Digital Library

[14]

Peter J. Cameron, Oligomorphic Permutation Groups, Cambridge University Press, Cambridge, 1990.

[15]

Complexity of Constraints - An Overview of Current Research Themes Result of a Dagstuhl Seminar, in: Lecture Notes in Computer Science, vol. 5250, Springer, 2008.

[16]

Reinhard Diestel, Graph Theory, Springer-Verlag, New York, 2005.

[17]

Tomás Feder, Moshe Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory, SIAM J. Comput., 28 (1999) 57-104.

Digital Library

[18]

Shawn Hedman, A First Course in Logic: An Introduction to Model Theory, Proof Theory, Computability, and Complexity, Oxford University Press, Inc., New York, NY, USA, 2004.

[19]

Pavol Hell, Jaroslav Nešetřil, On the complexity of H-coloring, J. Comb. Theory, Ser. B, 48 (1990) 92-110.

Digital Library

[20]

Pavol Hell, Jaroslav Nešetřil, Graphs and Homomorphisms, Oxford University Press, Oxford, 2004.

[21]

Wilfrid Hodges, A Shorter Model Theory, Cambridge University Press, Cambridge, 1997.

[22]

Peter Jeavons, David Cohen, Marc Gyssens, Closure properties of constraints, J. ACM, 44 (1997) 527-548.

Digital Library

[23]

David Marker, Model Theory: An Introduction, Springer, New York, 2002.

[24]

M. Maróti, R. McKenzie, Existence theorems for weakly symmetric operations, Algebra Univers., 59 (2008) 463-489.

[25]

Alexei Semenov, Sergey Soprunov, Vladimir Uspensky, The lattice of definability. Origins, recent developments, and further directions, in: Lecture Notes in Computer Science, vol. 8476, 2014, pp. 23-38.

Cited By

Amendola GManna MRicioppo A(2024)A logic-based framework for characterizing nexus of similarity within knowledge basesInformation Sciences: an International Journal10.1016/j.ins.2024.120331664:COnline publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.120331
Bodirsky MMartin BMottet A(2018)Discrete Temporal Constraint Satisfaction ProblemsJournal of the ACM10.1145/315483265:2(1-41)Online publication date: 6-Feb-2018
https://dl.acm.org/doi/10.1145/3154832

Distance constraint satisfaction problems
1. Theory of computation

Recommendations

Full Constraint Satisfaction Problems

Feder and Vardi have conjectured that all constraint satisfaction problems to a fixed structure (constraint language) are polynomial or NP-complete. This so-called dichotomy conjecture remains open, although it has been proved in a number of special ...
Complexity of Approximating CSP with Balance / Hard Constraints

We study two natural extensions of Constraint Satisfaction Problems (CSPs). Balance-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of Hard-Max-CSP consists of soft constraints ...
Constraint satisfaction tractability from semi-lattice operations on infinite sets

A famous result by Jeavons, Cohen, and Gyssens shows that every Constraint Satisfaction Problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. This is one of the basic facts for the so-called ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 247, Issue C

April 2016

314 pages

ISSN:0890-5401

Issue’s Table of Contents

Copyright © Elsevier Inc.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 April 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Amendola GManna MRicioppo A(2024)A logic-based framework for characterizing nexus of similarity within knowledge basesInformation Sciences: an International Journal10.1016/j.ins.2024.120331664:COnline publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.120331
Bodirsky MMartin BMottet A(2018)Discrete Temporal Constraint Satisfaction ProblemsJournal of the ACM10.1145/315483265:2(1-41)Online publication date: 6-Feb-2018
https://dl.acm.org/doi/10.1145/3154832

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents