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
Acyclic orders, partition schemes and CSPs: Unified hardness proofs and improved algorithms
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering. (TCSLAB)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. (TCSLAB)
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering. (TCSLAB)ORCID iD: 0000-0002-2884-9837
2021 (English)In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 296, article id 103505Article in journal (Refereed) Published
Abstract [en]

Many computational problems arising in, for instance, artificial intelligence can be realized as infinite-domain constraint satisfaction problems (CSPs) based on partition schemes: a set of pairwise disjoint binary relations (containing the equality relation) whose union spans the underlying domain and which is closed under converse. We first consider partition schemes that contain an acyclic order and where the constraint language contains all unions of the basic relations; such CSPs are frequently occurring in e.g. temporal and spatial reasoning. We identify properties of such orders which, when combined, are sufficient to establish NP-hardness of the CSP and strong lower bounds under the exponential-time hypothesis, even for degree-bounded problems. This result explains, in a uniform way, many existing hardness results from the literature, and shows that it is impossible to obtain subexponential time algorithms unless the exponential-time hypothesis fails. However, some of these problems (including several important temporal problems), despite likely not being solvable in subexponential time, admit non-trivial improved exponential-time algorithm, and we present a novel improved algorithm for RCC-8 and related formalisms.

Place, publisher, year, edition, pages
Elsevier, 2021. Vol. 296, article id 103505
Keywords [en]
Constraint satisfaction problems, Infinite domains, Partition schemes, Lower bounds
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-175145DOI: 10.1016/j.artint.2021.103505ISI: 000648650600003OAI: oai:DiVA.org:liu-175145DiVA, id: diva2:1545895
Note

Funding: Wallenberg AI, Autonomous Systems and Software Program (WASP) - Knut and Alice Wallenberg Foundation; Swedish Research Council (VR)Swedish Research Council [2017-04112]; VRSwedish Research Council [2019-03690]

Available from: 2021-04-20 Created: 2021-04-20 Last updated: 2021-06-01Bibliographically approved

Open Access in DiVA

fulltext(484 kB)185 downloads
File information
File name FULLTEXT01.pdfFile size 484 kBChecksum SHA-512
58603b4af1e6fe90f0e54e53967fadc8c3c008bc40480c016f268613db66eacc615abfa888fc3f1d4864c7541bef396ca68a996806bf819c3a8c73dedeb3f6ab
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Authority records

Jonsson, PeterLagerkvist, VictorOsipov, George

Search in DiVA

By author/editor
Jonsson, PeterLagerkvist, VictorOsipov, George
By organisation
Software and SystemsFaculty of Science & Engineering
In the same journal
Artificial Intelligence
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 185 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: 185 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