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

Direct link
Alternative names
Publications (10 of 101) Show all publications
Jonsson, P. & Lagerkvist, V. (2023). General Lower Bounds and Improved Algorithms for Infinite–Domain CSPs. Algorithmica, 85(1), 188-215
Open this publication in new window or tab >>General Lower Bounds and Improved Algorithms for Infinite–Domain CSPs
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
Keywords
Constraint satisfaction, Infinite domains, Equality languages, Fine-grained complexity, Lower bounds
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-198447 (URN)10.1007/s00453-022-01017-8 (DOI)000839434400001 ()2-s2.0-85135869960 (Scopus ID)
Funder
Swedish Research Council, 2017-04112Swedish Research Council, 2019-03690
Available from: 2023-10-13 Created: 2023-10-13 Last updated: 2023-10-19Bibliographically approved
Gnad, D., Helmert, M., Jonsson, P. & Shleyfman, A. (2023). Planning over Integers: Compilations and Undecidability. In: : . Paper presented at ICAPS.
Open this publication in new window or tab >>Planning over Integers: Compilations and Undecidability
2023 (English)Conference paper, Published paper (Refereed)
Keywords
WASP
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-198698 (URN)
Conference
ICAPS
Available from: 2023-10-23 Created: 2023-10-23 Last updated: 2023-10-23
Shleyfman, A., Gnad, D. & Jonsson, P. (2023). Structurally Restricted Fragments of Numeric Planning – a Complexity Analysis. In: : . Paper presented at AAAI.
Open this publication in new window or tab >>Structurally Restricted Fragments of Numeric Planning – a Complexity Analysis
2023 (English)Conference paper, Published paper (Refereed)
Keywords
WASP
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-198694 (URN)
Conference
AAAI
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)Swedish Research Council, 2021-04371
Available from: 2023-10-23 Created: 2023-10-23 Last updated: 2023-10-23
Jonsson, P., Lagerkvist, V. & Osipov, G. (2021). Acyclic orders, partition schemes and CSPs: Unified hardness proofs and improved algorithms. Artificial Intelligence, 296, Article ID 103505.
Open this publication in new window or tab >>Acyclic orders, partition schemes and CSPs: Unified hardness proofs and improved algorithms
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
Keywords
Constraint satisfaction problems, Infinite domains, Partition schemes, Lower bounds
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-175145 (URN)10.1016/j.artint.2021.103505 (DOI)000648650600003 ()
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
Shleyfman, A. & Jonsson, P. (2021). Computational Complexity of Computing Symmetries in Finite-Domain Planning. The journal of artificial intelligence research, 70, 1183-1221
Open this publication in new window or tab >>Computational Complexity of Computing Symmetries in Finite-Domain Planning
2021 (English)In: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 70, p. 1183-1221Article in journal (Refereed) Published
Abstract [en]

Symmetry-based pruning is a powerful method for reducing the search effort in finitedomain planning. This method is based on exploiting an automorphism group connected to the ground description of the planning task - these automorphisms are known as structural symmetries. In particular, we are interested in the STRUCTSYM problem where the generators of this group are to be computed. It has been observed in practice that the STRUCTSYM problem is surprisingly easy to solve. We explain this phenomenon by showing that STRUCTSYM is GI-complete, i.e., the graph isomorphism problem is polynomial-time equivalent to it and, consequently, solvable in quasi-polynomial time. This implies that it is solvable substantially faster than most computationally hard problems encountered in AI. We accompany this result by identifying natural restrictions of the planning task and its causal graph that ensure that STRUCTSYM can be solved in polynomial time. Given that the STRUCTSYM problem is GI-complete and thus solvable quite efficiently, it is interesting to analyse if other symmetries (than those that are encompassed by the STRUCTSYM problem) can be computed and/or analysed efficiently, too. To this end, we present a highly negative result: checking whether there exists an automorphism of the state transition graph that maps one state s into another state t is a PSPACE-hard problem and, consequently, at least as hard as the planning problem itself.

Place, publisher, year, edition, pages
Palo Alto, CA, United States: AI Access Foundation, Inc., 2021
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:liu:diva-182818 (URN)10.1613/jair.1.12283 (DOI)000743970700005 ()2-s2.0-85104323369 (Scopus ID)
Note

Funding Agencies: Adams Fellowship Program of the Israel Academy of Sciences and Humanities; Swedish Research Council (VR) [2017-04112]

Available from: 2022-02-18 Created: 2022-02-18 Last updated: 2022-03-11Bibliographically approved
Jonsson, P., Lagerkvist, V. & Ordyniak, S. (2021). Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors. In: Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming: . Paper presented at International Conference on Principles and Practice of Constraint Programming, October 25-29, 2021 (pp. 32:1-32:20). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, 210
Open this publication in new window or tab >>Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors
2021 (English)In: Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming, Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik , 2021, Vol. 210, p. 32:1-32:20Conference paper, Published paper (Refereed)
Abstract [en]

A backdoor in a finite-domain CSP instance is a set of variables where each possible instantiation moves the instance into a polynomial-time solvable class. Backdoors have found many applications in artificial intelligence and elsewhere, and the algorithmic problem of finding such backdoors has consequently been intensively studied. Sioutis and Janhunen (KI, 2019) have proposed a generalised backdoor concept suitable for infinite-domain CSP instances over binary constraints. We generalise their concept into a large class of CSPs that allow for higher-arity constraints. We show that this kind of infinite-domain backdoors have many of the positive computational properties that finite-domain backdoors have: the associated computational problems are fixed-parameter tractable whenever the underlying constraint language is finite. On the other hand, we show that infinite languages make the problems considerably harder. 

Place, publisher, year, edition, pages
Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, 2021
Series
Leibniz International Proceedings in Informatics (LIPIcs), ISSN 1868-8969 ; 32
Keywords
Constraint Satisfaction Problems, Parameterised Complexity, Backdoors
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-198452 (URN)10.4230/LIPIcs.CP.2021.32 (DOI)9783959772112 (ISBN)
Conference
International Conference on Principles and Practice of Constraint Programming, October 25-29, 2021
Available from: 2023-10-13 Created: 2023-10-13 Last updated: 2023-10-18Bibliographically approved
Dabrowski, K. K., Jonsson, P., Ordyniak, S. & Osipov, G. (2020). Fine-Grained Complexity of Temporal Problems. In: KR2020: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning: . Paper presented at 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, Rhodes, Greece, September 12-18, 2020 (pp. 284-293). IJCAI-INT JOINT CONF ARTIF INTELL
Open this publication in new window or tab >>Fine-Grained Complexity of Temporal Problems
2020 (English)In: KR2020: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, IJCAI-INT JOINT CONF ARTIF INTELL , 2020, p. 284-293Conference paper, Published paper (Refereed)
Abstract [en]

Expressive temporal reasoning formalisms are essential for AI. One family of such formalisms consists of disjunctive extensions of the simple temporal problem (STP). Such extensions are well studied in the literature and they have many important applications. It is known that deciding satisfiability of disjunctive STPs is NP-hard, while the fine-grained complexity of such problems is virtually unexplored. We present novel algorithms that exploit structural properties of the solution space and prove, assuming the Exponential-Time Hypothesis, that their worst-case time complexity is close to optimal. Among other things, we make progress towards resolving a long-open question concerning whether Allens interval algebra can be solved in single-exponential time, by giving a 2(O(n log log n)) algorithm for the special case of unit-length intervals.

Place, publisher, year, edition, pages
IJCAI-INT JOINT CONF ARTIF INTELL, 2020
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-174923 (URN)10.24963/kr.2020/29 (DOI)000720083100028 ()9780999241172 (ISBN)
Conference
17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, Rhodes, Greece, September 12-18, 2020
Note

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

Available from: 2021-04-09 Created: 2021-04-09 Last updated: 2021-12-15Bibliographically approved
Jonsson, P. & Lagerkvist, V. (2020). Lower bounds and faster algorithms for equality constraints. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence: . Paper presented at International Joint Conference on Artificial Intelligence (IJCAI) (pp. 1784-1790). International Joint Conferences on Artificial Intelligence
Open this publication in new window or tab >>Lower bounds and faster algorithms for equality constraints
2020 (English)In: Proceedings of the 29th International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence , 2020, p. 1784-1790Conference paper, Published paper (Refereed)
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. 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(n log 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. © 2020 Inst. Sci. inf., Univ. Defence in Belgrade. All rights reserved.

Place, publisher, year, edition, pages
International Joint Conferences on Artificial Intelligence, 2020
Series
IJCAI International Joint Conference on Artificial Intelligence, ISSN 1045-0823
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-171245 (URN)000764196701126 ()2-s2.0-85097355261 (Scopus ID)9780999241165 (ISBN)0999241168 (ISBN)
Conference
International Joint Conference on Artificial Intelligence (IJCAI)
Available from: 2020-11-11 Created: 2020-11-11 Last updated: 2024-01-31
Bäckström, C., Jonsson, P. & Ordyniak, S. (2018). A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs. In: Vadim Bulitko, Sabine Storandt (Ed.), 11th Annual Symposium on Combinatorial Search: . Paper presented at 11th Annual Symposium on Combinatorial Search (SoCS-2018), Jul. 2018, Stockholm, Sweden (pp. 19-27). AAAI Press
Open this publication in new window or tab >>A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs
2018 (English)In: 11th Annual Symposium on Combinatorial Search / [ed] Vadim Bulitko, Sabine Storandt, AAAI Press, 2018, p. 19-27Conference paper, Published paper (Refereed)
Abstract [en]

Complexity analysis based on the causal graphs of planning instances has emerged as a highly important area of research. In particular, tractability results have led to new methods for the identification of domain-independent heuristics. Important early examples of such tractability results have been presented by, for instance, Brafman & Domshlak and Katz & Keyder. More general results based on polytrees and bounding certain parameters were subsequently derived by Aghighi et al. and Ståhlberg. We continue this line of research by analyzing cost-optimal planning restricted to instances with a polytree causal graph, bounded domain size and bounded depth (i.e. the length of the longest directed path in the causal graph). We show that no further restrictions are necessary for tractability, thus generalizing the previous results. Our approach is based on a novel method of closely analysing optimal plans: we recursively decompose the causal graph in a way that allows for bounding the number of variable changes as a function of the depth, using a reording argument and a comparison with prefix trees of known size. We can then transform the planning instances into constraint satisfaction instances; an idea that has previously been exploited by, for example, Brafman & Domshlak and Bäckström. This allows us to utilise efficient algorithms for constraint optimisation over tree-structured instances.

Place, publisher, year, edition, pages
AAAI Press, 2018
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-158236 (URN)10.1609/socs.v9i1.18455 (DOI)978-1-57735-802-2 (ISBN)
Conference
11th Annual Symposium on Combinatorial Search (SoCS-2018), Jul. 2018, Stockholm, Sweden
Note

Best paper award

Available from: 2019-06-26 Created: 2019-06-26 Last updated: 2023-09-22
Jonsson, P. & Lagerkvist, V. (2018). Why are CSPs based on partition schemes computationally hard?. In: Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science: . Paper presented at International Symposium on Mathematical Foundations of Computer Science.
Open this publication in new window or tab >>Why are CSPs based on partition schemes computationally hard?
2018 (English)In: Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018Conference paper, Published paper (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-171248 (URN)
Conference
International Symposium on Mathematical Foundations of Computer Science
Available from: 2020-11-11 Created: 2020-11-11 Last updated: 2021-09-21
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-5288-3330

Search in DiVA

Show all publications