liu.seSearch for publications in DiVA
Endre søk
Link to record
Permanent link

Direct link
Lagerkvist, Victor
Alternativa namn
Publikasjoner (10 av 29) Visa alla publikasjoner
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). IJCAI-INT JOINT CONF ARTIF INTELL
Åpne denne publikasjonen i ny fane eller vindu >>A Fast Algorithm for Consistency Checking Partially Ordered Time
2023 (engelsk)Inngår i: Proceedings of the 32nd International Joint Conference on Artificial Intelligence, IJCAI-INT JOINT CONF ARTIF INTELL , 2023, s. 1911-1918Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
IJCAI-INT JOINT CONF ARTIF INTELL, 2023
Emneord
Constraint Satisfaction and Optimization: CSO: Constraint satisfaction Knowledge Representation and Reasoning: KRR: Qualitative, geometric, spatial, and temporal reasoning
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-198448 (URN)10.24963/ijcai.2023/212 (DOI)001202344201111 ()9781956792034 (ISBN)
Konferanse
International Joint Conference on Artificial Intelligence, Macao, S.A.R, 19-25 August, 2023 
Merknad

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

Tilgjengelig fra: 2023-10-13 Laget: 2023-10-13 Sist oppdatert: 2024-08-27bibliografisk kontrollert
Jonsson, P. & Lagerkvist, V. (2023). General Lower Bounds and Improved Algorithms for Infinite–Domain CSPs. Algorithmica, 85(1), 188-215
Åpne denne publikasjonen i ny fane eller vindu >>General Lower Bounds and Improved Algorithms for Infinite–Domain CSPs
2023 (engelsk)Inngår i: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 85, nr 1, s. 188-215Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
Springer, 2023
Emneord
Constraint satisfaction, Infinite domains, Equality languages, Fine-grained complexity, Lower bounds
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-198447 (URN)10.1007/s00453-022-01017-8 (DOI)000839434400001 ()2-s2.0-85135869960 (Scopus ID)
Forskningsfinansiär
Swedish Research Council, 2017-04112Swedish Research Council, 2019-03690
Tilgjengelig fra: 2023-10-13 Laget: 2023-10-13 Sist oppdatert: 2024-03-14bibliografisk kontrollert
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). IJCAI-INT JOINT CONF ARTIF INTELL
Åpne denne publikasjonen i ny fane eller vindu >>Improved Algorithms for Allen’s Interval Algebra by Dynamic Programming with Sublinear Partitioning
2023 (engelsk)Inngår i: Proceedings of the 32nd International Joint Conference on Artificial Intelligence, IJCAI-INT JOINT CONF ARTIF INTELL , 2023, s. 1919-1926Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
IJCAI-INT JOINT CONF ARTIF INTELL, 2023
Emneord
Constraint Satisfaction and Optimization: CSO: Constraint satisfaction Knowledge Representation and Reasoning: KRR: Qualitative, geometric, spatial, and temporal reasoning
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-198449 (URN)10.24963/ijcai.2023/213 (DOI)001202344202001 ()9781956792034 (ISBN)
Konferanse
International Joint Conference on Artificial Intelligence, Macao, S.A.R, 19-25 August, 2023
Merknad

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

Tilgjengelig fra: 2023-10-13 Laget: 2023-10-13 Sist oppdatert: 2024-08-27bibliografisk kontrollert
Eriksson, L. & Lagerkvist, V. (2022). A Multivariate Complexity Analysis of Qualitative Reasoning Problems. In: Luc De Raedt (Ed.), Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI-22): . Paper presented at International Joint Conference on Artificial Intelligence, Messe Wien, Vienna, Austria, July 23-29, 2022 (pp. 1804-1810). International Joint Conferences on Artificial Intelligence
Åpne denne publikasjonen i ny fane eller vindu >>A Multivariate Complexity Analysis of Qualitative Reasoning Problems
2022 (engelsk)Inngår i: Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI-22) / [ed] Luc De Raedt, International Joint Conferences on Artificial Intelligence , 2022, s. 1804-1810Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Qualitative reasoning is an important subfeld ofartifcial intelligence where one describes relationships with qualitative, rather than numerical, relations. Many such reasoning tasks, e.g., ALLEN’SINTERVAL ALGEBRA, can be solved in 2O(n·log n) time, but single-exponential running times 2O(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 coarsegrained parameter k expected to be relatively small.We introduce the classes FPE and XE of problems solvable in f(k) · 2O(n), respectively f(k)n,time, and prove several fundamental properties ofthese classes. We proceed by studying temporal reasoning problems and (1) show that the PARTIALLYORDERED TIME problem of effective width k is solvable in 16kn time and is thus included in XE, and (2) that the network consistency problem for ALLEN’S INTERVAL ALGEBRA with no intervaloverlapping with more than k others is solvable in (2nk)2k· 2n time and is included in FPE. Our multivariate approach is in no way limited to these tospecifc problems and may be a generally useful approach for obtaining single-exponential algorithms. 

sted, utgiver, år, opplag, sider
International Joint Conferences on Artificial Intelligence, 2022
Serie
Proceedings of the International Joint Conference on Artificial Intelligence, ISSN 1045-0823
Emneord
Constraint Satisfaction and Optimization: Constraint Satisfaction
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-198450 (URN)10.24963/ijcai.2022/251 (DOI)2-s2.0-85137850976 (Scopus ID)9781956792003 (ISBN)
Konferanse
International Joint Conference on Artificial Intelligence, Messe Wien, Vienna, Austria, July 23-29, 2022
Tilgjengelig fra: 2023-10-13 Laget: 2023-10-13 Sist oppdatert: 2024-09-23bibliografisk kontrollert
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
Åpne denne publikasjonen i ny fane eller vindu >>C-Maximal Strong Partial Clones and the Inclusion Structure of Boolean Weak Bases
2022 (engelsk)Inngår i: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, E-ISSN 1542-3999, Vol. 38, nr 3-4, s. 333-353Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
Philadelphia, PA, United States: Old City Publishing, 2022
Emneord
Universal algebra, clone theory, partial clone theory, weak bases
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-182644 (URN)000745038100004 ()
Tilgjengelig fra: 2022-02-03 Laget: 2022-02-03 Sist oppdatert: 2022-02-10bibliografisk kontrollert
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.
Åpne denne publikasjonen i ny fane eller vindu >>Acyclic orders, partition schemes and CSPs: Unified hardness proofs and improved algorithms
2021 (engelsk)Inngår i: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 296, artikkel-id 103505Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
Elsevier, 2021
Emneord
Constraint satisfaction problems, Infinite domains, Partition schemes, Lower bounds
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-175145 (URN)10.1016/j.artint.2021.103505 (DOI)000648650600003 ()
Merknad

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]

Tilgjengelig fra: 2021-04-20 Laget: 2021-04-20 Sist oppdatert: 2021-06-01bibliografisk kontrollert
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
Åpne denne publikasjonen i ny fane eller vindu >>Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
2021 (engelsk)Inngår i: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 117, s. 23-39Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
Elsevier, 2021
Emneord
Clone theory; Universal algebra; Satisfiability problems; Constraint satisfaction problems; Inverse problems
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-173173 (URN)10.1016/j.jcss.2020.10.004 (DOI)000606822100002 ()
Konferanse
46th International Colloquium on Automata, Languages and Programming (ICALP), Patras, GREECE, jul 09-12, 2019
Merknad

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

Tilgjengelig fra: 2021-02-10 Laget: 2021-02-10 Sist oppdatert: 2022-11-18bibliografisk kontrollert
Eriksson, L. & Lagerkvist, V. (2021). Improved Algorithms for Allen’s Interval Algebra: a Dynamic Programming Approach. In: Zhi-Hua Zhou (Ed.), Proceedings of the 30th International Joint Conference on Artificial Intelligence: . Paper presented at the Thirtieth International Joint Conference on Artificial Intelligence, Montreal, 19-27 August 2021 (pp. 1873-1879). International Joint Conferences on Artificial Intelligence
Åpne denne publikasjonen i ny fane eller vindu >>Improved Algorithms for Allen’s Interval Algebra: a Dynamic Programming Approach
2021 (engelsk)Inngår i: Proceedings of the 30th International Joint Conference on Artificial Intelligence / [ed] Zhi-Hua Zhou, International Joint Conferences on Artificial Intelligence , 2021, s. 1873-1879Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
International Joint Conferences on Artificial Intelligence, 2021
Serie
Proceedings of the International Joint Conference on Artificial Intelligence, ISSN 1045-0823
Emneord
Knowledge Representation and Reasoning: Qualitative, Geometric, Spatial, Temporal Reasoning Constraints and SAT: Constraint Satisfaction
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-198451 (URN)10.24963/ijcai.2021/258 (DOI)001202335501130 ()2-s2.0-85125470528 (Scopus ID)9780999241196 (ISBN)
Konferanse
the Thirtieth International Joint Conference on Artificial Intelligence, Montreal, 19-27 August 2021
Tilgjengelig fra: 2023-10-13 Laget: 2023-10-13 Sist oppdatert: 2024-09-23bibliografisk kontrollert
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
Åpne denne publikasjonen i ny fane eller vindu >>Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors
2021 (engelsk)Inngår i: 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, s. 32:1-32:20Konferansepaper, Publicerat paper (Fagfellevurdert)
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. 

sted, utgiver, år, opplag, sider
Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, 2021
Serie
Leibniz International Proceedings in Informatics (LIPIcs), ISSN 1868-8969 ; 32
Emneord
Constraint Satisfaction Problems, Parameterised Complexity, Backdoors
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-198452 (URN)10.4230/LIPIcs.CP.2021.32 (DOI)9783959772112 (ISBN)
Konferanse
International Conference on Principles and Practice of Constraint Programming, October 25-29, 2021
Tilgjengelig fra: 2023-10-13 Laget: 2023-10-13 Sist oppdatert: 2023-10-18bibliografisk kontrollert
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
Åpne denne publikasjonen i ny fane eller vindu >>Lower bounds and faster algorithms for equality constraints
2020 (engelsk)Inngår i: Proceedings of the 29th International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence , 2020, s. 1784-1790Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
International Joint Conferences on Artificial Intelligence, 2020
Serie
IJCAI International Joint Conference on Artificial Intelligence, ISSN 1045-0823
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-171245 (URN)000764196701126 ()2-s2.0-85097355261 (Scopus ID)9780999241165 (ISBN)0999241168 (ISBN)
Konferanse
International Joint Conference on Artificial Intelligence (IJCAI)
Tilgjengelig fra: 2020-11-11 Laget: 2020-11-11 Sist oppdatert: 2024-01-31
Organisasjoner