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

Direct link
Lagerkvist, Victor
Alternative names
Publications (10 of 29) Show all publications
Eriksson, L. & Lagerkvist, V. (2023). A Fast Algorithm for Consistency Checking Partially Ordered Time. In: Proceedings of the 32nd International Joint Conference on Artificial Intelligence: . Paper presented at International Joint Conference on Artificial Intelligence, Macao, S.A.R, 19-25 August, 2023  (pp. 1911-1918).
Open this publication in new window or tab >>A Fast Algorithm for Consistency Checking Partially Ordered Time
2023 (English)In: Proceedings of the 32nd International Joint Conference on Artificial Intelligence, 2023, p. 1911-1918Conference paper, Published paper (Refereed)
Abstract [en]

Partially ordered models of time occur naturally in applications where agents/processes cannot perfectly communicate with each other, and can be traced back to the seminal work of Lamport. In this paper we consider the problem of deciding if a (likely incomplete) description of a system of events is consistent, the network consistency problem for the point algebra of partially ordered time (POT). While the classical complexity of this problem has been fully settled, comparably little is known of the fine-grained complexity of POT except that it can be solved in O*((0.368n)^n) time by enumerating ordered partitions. We construct a much faster algorithm with a run-time bounded by O*((0.26n)^n), which, e.g., is roughly 1000 times faster than the naive enumeration algorithm in a problem with 20 events. This is achieved by a sophisticated enumeration of structures similar to total orders, which are then greedily expanded toward a solution. While similar ideas have been explored earlier for related problems it turns out that the analysis for POT is non-trivial and requires significant new ideas.

Keywords
Constraint Satisfaction and Optimization: CSO: Constraint satisfaction Knowledge Representation and Reasoning: KRR: Qualitative, geometric, spatial, and temporal reasoning
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-198448 (URN)10.24963/ijcai.2023/212 (DOI)
Conference
International Joint Conference on Artificial Intelligence, Macao, S.A.R, 19-25 August, 2023 
Available from: 2023-10-13 Created: 2023-10-13 Last updated: 2023-10-18Bibliographically approved
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
Eriksson, L. & Lagerkvist, V. (2023). Improved Algorithms for Allen’s Interval Algebra by Dynamic Programming with Sublinear Partitioning. In: Proceedings of the 32nd International Joint Conference on Artificial Intelligence: . Paper presented at International Joint Conference on Artificial Intelligence, Macao, S.A.R, 19-25 August, 2023 (pp. 1919-1926).
Open this publication in new window or tab >>Improved Algorithms for Allen’s Interval Algebra by Dynamic Programming with Sublinear Partitioning
2023 (English)In: Proceedings of the 32nd International Joint Conference on Artificial Intelligence, 2023, p. 1919-1926Conference paper, Published paper (Refereed)
Abstract [en]

Allen's interval algebra is one of the most well-known calculi in qualitative temporal reasoning with numerous applications in artificial intelligence. Very recently, there has been a surge of improvements in the fine-grained complexity of NP-hard reasoning tasks in this algebra, which has improved the running time from the naive 2^O(n^2) to O*((1.0615n)^n), and even faster algorithms are known for unit intervals and the case when we a bounded number of overlapping intervals. Despite these improvements the best known lower bound is still only 2^o(n) under the exponential-time hypothesis and major improvements in either direction seemingly require fundamental advances in computational complexity. In this paper we propose a novel framework for solving NP-hard qualitative reasoning problems which we refer to as dynamic programming with sublinear partitioning. Using this technique we obtain a major improvement of O*((cn/log(n))^n) for Allen's interval algebra. To demonstrate that the technique is applicable to further problem domains we apply it to a problem in qualitative spatial reasoning, the cardinal direction calculus, and solve it in O*((cn/log(n))^(2n/3)) time. Hence, not only do we significantly advance the state-of-the-art for NP-hard qualitative reasoning problems, but obtain a novel algorithmic technique that is likely applicable to many problems where 2^O(n) time algorithms are unlikely.

Keywords
Constraint Satisfaction and Optimization: CSO: Constraint satisfaction Knowledge Representation and Reasoning: KRR: Qualitative, geometric, spatial, and temporal reasoning
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-198449 (URN)10.24963/ijcai.2023/213 (DOI)
Conference
International Joint Conference on Artificial Intelligence, Macao, S.A.R, 19-25 August, 2023
Available from: 2023-10-13 Created: 2023-10-13 Last updated: 2023-10-18Bibliographically approved
Eriksson, L. & Lagerkvist, V. (2022). A Multivariate Complexity Analysis of Qualitative Reasoning Problems. In: Proceedings of the 31st International Joint Conference on Artificial Intelligence: . Paper presented at International Joint Conference on Artificial Intelligence, Messe Wien, Vienna, Austria, July 23-29, 2022 (pp. 1804-1810).
Open this publication in new window or tab >>A Multivariate Complexity Analysis of Qualitative Reasoning Problems
2022 (English)In: Proceedings of the 31st International Joint Conference on Artificial Intelligence, 2022, p. 1804-1810Conference paper, Published paper (Refereed)
Abstract [en]

Qualitative reasoning is an important subfield of artificial intelligence where one describes relationships with qualitative, rather than numerical, relations. Many such reasoning tasks, e.g., Allen's interval algebra, can be solved in 2^O(n*log n) time, but single-exponential running times 2^O(n) are currently far out of reach. In this paper we consider single-exponential algorithms via a multivariate analysis consisting of a fine-grained parameter n (e.g., the number of variables) and a coarse-grained parameter k expected to be relatively small. We introduce the classes FPE and XE of problems solvable in f(k)*2^O(n), respectively f(k)^n, time, and prove several fundamental properties of these classes. We proceed by studying temporal reasoning problems and (1) show that the partially ordered time problem of effective width k is solvable in 16^{kn} time and is thus included in XE, and (2) that the network consistency problem for Allen's interval algebra with no interval overlapping with more than k others is solvable in (2nk)^{2k}*2^n time and is included in FPE. Our multivariate approach is in no way limited to these to specific problems and may be a generally useful approach for obtaining single-exponential algorithms.

Keywords
Constraint Satisfaction and Optimization: Constraint Satisfaction
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-198450 (URN)10.24963/ijcai.2022/251 (DOI)
Conference
International Joint Conference on Artificial Intelligence, Messe Wien, Vienna, Austria, July 23-29, 2022
Available from: 2023-10-13 Created: 2023-10-13 Last updated: 2023-10-18Bibliographically approved
Lagerkvist, V. & Roy, B. (2022). C-Maximal Strong Partial Clones and the Inclusion Structure of Boolean Weak Bases. Journal of Multiple-Valued Logic and Soft Computing, 38(3-4), 333-353
Open this publication in new window or tab >>C-Maximal Strong Partial Clones and the Inclusion Structure of Boolean Weak Bases
2022 (English)In: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, E-ISSN 1542-3999, Vol. 38, no 3-4, p. 333-353Article in journal (Refereed) Published
Abstract [en]

Strong partial clones are composition closed sets of partial operations containing all partial projections, characterizable as partial polymorphisms of sets of relations Γ (pPol(Γ)). If C is a clone it is known that the set of all strong partial clones whose total component equals C, has a greatest element pPol(Γω), where Γω is called a weak base. Weak bases have seen applications in computer science due to their usefulness for proving complexity classifications for constraint satisfaction related problems. In this article we (1) completely describe the inclusion structure between pPol(Γω), pPol(Δω) for all Boolean weak bases Γω and Δω and (2) in many such cases prove that the strong partial clones in question uniquely cover each other.

Place, publisher, year, edition, pages
Philadelphia, PA, United States: Old City Publishing, 2022
Keywords
Universal algebra, clone theory, partial clone theory, weak bases
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-182644 (URN)000745038100004 ()
Available from: 2022-02-03 Created: 2022-02-03 Last updated: 2022-02-10Bibliographically approved
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
Lagerkvist, V. & Roy, B. (2021). Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem. Paper presented at 46th International Colloquium on Automata, Languages and Programming (ICALP), Patras, GREECE, jul 09-12, 2019. Journal of computer and system sciences (Print), 117, 23-39
Open this publication in new window or tab >>Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
2021 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 117, p. 23-39Article in journal (Refereed) Published
Abstract [en]

The inverse satisfiability problem over a set of relations Gamma (INv-SAT(Gamma)) is the problem of deciding whether a relation R can be defined as the set of models of a SAT(Gamma) instance. Kavvadias and Sideri (1998) [15] obtained a dichotomy between P and co-NP-complete for finite r containing the two constant Boolean relations. However, for arbitrary constraint languages the complexity has been wide open, and in this article we finally prove a complete dichotomy theorem for finite languages. Kavvadias and Sideris techniques are not applicable and we have to turn to the more recent algebraic approach based on partial polymorphisms. We also study the complexity of the inverse constraint satisfaction problem prove a general hardness result, which in particular resolves the complexity of INvERSE k-COLOURING, mentioned as an open problem in Chen (2008) [8]. (C) 2020 Elsevier Inc. All rights reserved.

Place, publisher, year, edition, pages
Elsevier, 2021
Keywords
Clone theory; Universal algebra; Satisfiability problems; Constraint satisfaction problems; Inverse problems
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-173173 (URN)10.1016/j.jcss.2020.10.004 (DOI)000606822100002 ()
Conference
46th International Colloquium on Automata, Languages and Programming (ICALP), Patras, GREECE, jul 09-12, 2019
Note

Funding Agencies|German Research Foundation (DFG)German Research Foundation (DFG) [622397]; Swedish Research Council (VR)Swedish Research Council [2019-03690]; National Graduate School in Computer Science(CUGS), Sweden

Available from: 2021-02-10 Created: 2021-02-10 Last updated: 2022-11-18Bibliographically approved
Eriksson, L. & Lagerkvist, V. (2021). Improved Algorithms for Allen’s Interval Algebra: a Dynamic Programming Approach. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence: . Paper presented at International Joint Conference on Artificial Intelligence, 19-26 August, 2021 (pp. 1873-1879).
Open this publication in new window or tab >>Improved Algorithms for Allen’s Interval Algebra: a Dynamic Programming Approach
2021 (English)In: Proceedings of the 30th International Joint Conference on Artificial Intelligence, 2021, p. 1873-1879Conference paper, Published paper (Refereed)
Abstract [en]

The constraint satisfaction problem (CSP) is an important framework in artificial intelligence used to model e.g. qualitative reasoning problems such as Allen's interval algebra A. There is strong practical incitement to solve CSPs as efficiently as possible, and the classical complexity of temporal CSPs, including A, is well understood. However, the situation is more dire with respect to running time bounds of the form O(f(n)) (where n is the number of variables) where existing results gives a best theoretical upper bound 2^O(n * log n) which leaves a significant gap to the best (conditional) lower bound 2^o(n). In this paper we narrow this gap by presenting two novel algorithms for temporal CSPs based on dynamic programming. The first algorithm solves temporal CSPs limited to constraints of arity three in O(3^n) time, and we use this algorithm to solve A in O((1.5922n)^n) time. The second algorithm tackles A directly and solves it in O((1.0615n)^n), implying a remarkable improvement over existing methods since no previously published algorithm belongs to O((cn)^n) for any c. We also extend the latter algorithm to higher dimensions box algebras where we obtain the first explicit upper bound.

Keywords
Knowledge Representation and Reasoning: Qualitative, Geometric, Spatial, Temporal Reasoning Constraints and SAT: Constraint Satisfaction
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-198451 (URN)10.24963/ijcai.2021/258 (DOI)
Conference
International Joint Conference on Artificial Intelligence, 19-26 August, 2021
Available from: 2023-10-13 Created: 2023-10-13 Last updated: 2023-10-18Bibliographically 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
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
Organisations

Search in DiVA

Show all publications