liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
General Lower Bounds and Improved Algorithms for Infinite–Domain CSPs
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-5288-3330
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
2023 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 85, no 1, p. 188-215Article in journal (Refereed) Published
Abstract [en]

We study the fine-grained complexity of NP-complete, infinite-domain constraint satisfaction problems (CSPs) parameterised by a set of first-order definable relations (with equality). Such CSPs are of central importance since they form a subclass of any infinite-domain CSP parameterised by a set of first-order definable relations over a relational structure (possibly containing more than just equality). We prove that under the randomised exponential-time hypothesis it is not possible to find c>1 such that a CSP over an arbitrary finite equality language is solvable in O(cn) time (n is the number of variables). Stronger lower bounds are possible for infinite equality languages where we rule out the existence of 2o(nlog⁡n) time algorithms; a lower bound which also extends to satisfiability modulo theories solving for an arbitrary background theory. Despite these lower bounds we prove that for each c>1 there exists an NP-hard equality CSP solvable in O(cn) time. Lower bounds like these immediately ask for closely matching upper bounds, and we prove that a CSP over a finite equality language is always solvable in O(cn) time for a fixed c, and manage to extend this algorithm to the much broader class of CSPs where constraints are formed by first-order formulas over a unary structure.

Place, publisher, year, edition, pages
Springer, 2023. Vol. 85, no 1, p. 188-215
Keywords [en]
Constraint satisfaction, Infinite domains, Equality languages, Fine-grained complexity, Lower bounds
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-198447DOI: 10.1007/s00453-022-01017-8ISI: 000839434400001Scopus ID: 2-s2.0-85135869960OAI: oai:DiVA.org:liu-198447DiVA, id: diva2:1804535
Funder
Swedish Research Council, 2017-04112Swedish Research Council, 2019-03690Available from: 2023-10-13 Created: 2023-10-13 Last updated: 2024-03-14Bibliographically approved

Open Access in DiVA

fulltext(804 kB)161 downloads
File information
File name FULLTEXT03.pdfFile size 804 kBChecksum SHA-512
a11fe9afb8ab0573e72e17f2fa4dca4c7fe8f49a5e3ea24d96c2d6d42d7024423f38bf5bf2004132a07388654dc5b9f06bd0598ea33250eb06c5c11c2370ff8e
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Jonsson, PeterLagerkvist, Victor

Search in DiVA

By author/editor
Jonsson, PeterLagerkvist, Victor
By organisation
Software and SystemsFaculty of Science & Engineering
In the same journal
Algorithmica
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 162 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 192 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf