liu.seSearch for publications in DiVA
Change search
Refine search result
1 - 39 of 39
CiteExportLink to result list
Permanent 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
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Eriksson, Leif
    et al.
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    A Fast Algorithm for Consistency Checking Partially Ordered Time2023In: Proceedings of the 32nd International Joint Conference on Artificial Intelligence, 2023, p. 1911-1918Conference 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.

  • 2.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    General Lower Bounds and Improved Algorithms for Infinite–Domain CSPs2023In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 85, no 1, p. 188-215Article in journal (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 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.

  • 3.
    Eriksson, Leif
    et al.
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Improved Algorithms for Allen’s Interval Algebra by Dynamic Programming with Sublinear Partitioning2023In: Proceedings of the 32nd International Joint Conference on Artificial Intelligence, 2023, p. 1919-1926Conference 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.

  • 4.
    Eriksson, Leif
    et al.
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    A Multivariate Complexity Analysis of Qualitative Reasoning Problems2022In: Proceedings of the 31st International Joint Conference on Artificial Intelligence, 2022, p. 1804-1810Conference 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.

  • 5.
    Couceiro, Miguel
    et al.
    Univ Lorraine, France.
    Haddad, Lucien
    Royal Mil Coll Canada, Canada.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    A Survey on the Fine-grained Complexity of Constraint Satisfaction Problems Based on Partial Polymorphisms2022In: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, E-ISSN 1542-3999, Vol. 38, no 1-2, p. 115-136Article in journal (Refereed)
    Abstract [en]

    Constraint satisfaction problems (CSPs) are combinatorial problems with strong ties to universal algebra and clone theory. The recently proved CSP dichotomy theorem states that each finite-domain CSP is either solvable in polynomial time, or that it is NP-complete. However, among the intractable CSPs there is a seemingly large variance in how fast they can be solved by exponential-time algorithms, which cannot be explained by the classical algebraic approach based on polymorphisms. In this contribution we will survey an alternative approach based on partial polymorphisms, which is useful for studying the fine-grained complexity of NP-complete CSPs. Moreover, we will state and discuss some challenging open problems in this research field.

  • 6.
    Baril, Ambroise
    et al.
    Univ Lorraine, France.
    Couceiro, Miguel
    Univ Lorraine, France.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    An Algebraic Approach Towards the Fine-Grained Complexity of Graph Coloring Problems2022In: 2022 IEEE 52ND INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL 2022), IEEE COMPUTER SOC , 2022, p. 94-99Conference paper (Refereed)
    Abstract [en]

    In this paper we are interested in the fine-grained complexity of determining whether there is an homomorphism from an input graph G to a fixed graph H (the H-coloring problem). The starting point is the observation that these problems can be formulated in the language of CSPs, and that (partial) polymorphisms of binary relations are of paramount importance in the study of complexity classes of such CSPs. Thus, we first investigate the expressivity of binary symmetric relations E-H and their corresponding (partial) polymorphisms pPol(E-H). For irreflexive graphs we observe that there is no pair of graphs H and H such that pPol(E-H) subset of pPol(E-H), unless E-H = theta or H = H. More generally we show the existence of an nary relation R whose partial polymorphisms strictly subsume those of H and such that CSP(R) is NP-complete if and only if H contains an odd cycle of length at most n. Motivated by this we also describe the sets of total polymorphisms of every nontrivial clique, every odd cycle, as well as certain cores. We finish the paper with some noteworthy questions for future research.

  • 7.
    Lagerkvist, Victor
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Roy, Biman
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    C-Maximal Strong Partial Clones and the Inclusion Structure of Boolean Weak Bases2022In: 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)
    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.

  • 8.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Ordyniak, Sebastian
    Univ Leeds, England.
    Computational Short Cuts in Infinite Domain Constraint Satisfaction2022In: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 75, p. 793-831Article in journal (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 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: the general backdoor detection problem is W[2]-hard and fixed-parameter tractability is ruled out under standard complexity-theoretic assumptions. We demonstrate that backdoors may have suboptimal behaviour on binary constraints| this is detrimental from an AI perspective where binary constraints are predominant in, for instance, spatiotemporal applications. In response to this, we introduce sidedoors as an alternative to backdoors. The fundamental computational problems for sidedoors remain fixed-parameter tractable for finite constraint language (possibly also containing non-binary relations). Moreover, the sidedoor approach has appealing computational properties that sometimes leads to faster algorithms than the backdoor approach.

    Download full text (pdf)
    fulltext
  • 9.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    General Lower Bounds and Improved Algorithms for Infinite-Domain CSPs2022In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 85, p. 188-215Article in journal (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 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(c(n)) time (n is the number of variables). Stronger lower bounds are possible for infinite equality languages where we rule out the existence of 2(o(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(c(n)) 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(c(n)) 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.

  • 10.
    Lagerkvist, Victor
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Wahlstrom, Magnus
    Royal Holloway Univ London, England.
    The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems2022In: ACM Transactions on Computation Theory, ISSN 1942-3454, E-ISSN 1942-3462, Vol. 14, no 1, article id 2Article in journal (Refereed)
    Abstract [en]

    We study the fine-grained complexity of NP-complete satisfiability (SAT) problems and constraint satisfaction problems (CSPs) in the context of the strong exponential-time hypothesis (SETH), showing non-trivial lower and upper bounds on the running time. Here, by a non-trivial lower bound for a problem SAT(Gamma) (respectively CSP(Gamma)) with constraint language F, we mean a value c(0) > 1 such that the problem cannot be solved in time O(c(n)) for any c < c(0) unless SETH is false, while a non-trivial upper bound is simply an algorithm for the problem running in time O(c(n)) for some c < 2. Such lower bounds have proven extremely elusive, and except for cases where c(0) = 2 effectively no such previous bound was known. We achieve this by employing an algebraic framework, studying constraint languages r in terms of their algebraic properties. We uncover a powerful algebraic framework where a mild restriction on the allowed constraints offers a concise algebraic characterization. On the relational side we restrict ourselves to Boolean languages closed under variable negation and partial assignment, called sign-symmetric languages. On the algebraic side this results in a description via partial operations arising from system of identities, with a close connection to operations resulting in tractable CSPs, such as near unanimity operations and edge operations. Using this connection we construct improved algorithms for several interesting classes of sign-symmetric languages, and prove explicit lower bounds under SETH. Thus, we find the first example of an NP-complete SAT problem with a non-trivial algorithm which also admits a non-trivial lower bound under SETH. This suggests a dichotomy conjecture with a close connection to the CSP dichotomy theorem: an NP-complete SAT problem admits an improved algorithm if and only if it admits a non-trivial partial invariant of the above form.

    Download full text (pdf)
    fulltext
  • 11.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Osipov, George
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Acyclic orders, partition schemes and CSPs: Unified hardness proofs and improved algorithms2021In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 296, article id 103505Article in journal (Refereed)
    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.

    Download full text (pdf)
    fulltext
  • 12.
    Lagerkvist, Victor
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Roy, Biman
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem2021In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 117, p. 23-39Article in journal (Refereed)
    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.

    Download full text (pdf)
    fulltext
  • 13.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Roy, Biman
    Drabantgatan 5, S-58214 Linkoping, Ostergotland, Sweden.
    Fine-Grained Time Complexity of Constraint Satisfaction Problems2021In: ACM Transactions on Computation Theory, ISSN 1942-3454, E-ISSN 1942-3462, Vol. 13, no 1, article id 2Article in journal (Refereed)
    Abstract [en]

    We study the constraint satisfaction problem (CSP) parameterized by a constraint language F (CSP(F)) and how the choice of F affects its worst-case time complexity. Under the exponential-time hypothesis (ETH), we rule out the existence of subexponential algorithms for finite-domain NP-complete CSP(F) problems. This extends to certain infinite-domain CSPs and structurally restricted problems. For CSPs with finite domain D and where all unary relations are available, we identify a relation S-D such that the time complexity of the NP-complete problem CSP({S-D}) is a lower bound for all NP-complete CSPs of this kind. We also prove that the time complexity of CSP({S-D}) strictly decreases when vertical bar D vertical bar increases (unless the ETH is false) and provide stronger complexity results in the special case when vertical bar D vertical bar = 3.

    Download full text (pdf)
    fulltext
  • 14.
    Eriksson, Leif
    et al.
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Improved Algorithms for Allen’s Interval Algebra: a Dynamic Programming Approach2021In: Proceedings of the 30th International Joint Conference on Artificial Intelligence, 2021, p. 1873-1879Conference 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.

  • 15.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Lower bounds and faster algorithms for equality constraints2021In: Proceedings of the 29th International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence , 2021, p. 1784-1790Conference 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.

  • 16.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.
    Ordyniak, Sebastian
    Algorithms Group, University of Sheffield, UK.
    Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors2021In: 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 (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. 

  • 17.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Schmidt, Johannes
    Jonkoping Univ, Sweden.
    Uppman, Hannes
    Linköping, Sweden.
    The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems2021In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 892Article in journal (Refereed)
    Abstract [en]

    Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Algebraic techniques introduced by Jonsson et al. (2017) [4] show that the fine-grained time complexity of the parameterized SAT(middot) problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation R such that SAT(R) can be solved at least as fast as any other NP-hard SAT(middot) problem. In this paper we extend this method and show that such languages also exist for the surjective SAT problem, the max ones problem, the propositional abduction problem, and the Boolean valued constraint satisfaction problem over finite-valued constraint languages. These languages may be interesting when investigating the borderline between polynomial time, subexponential time and exponential-time algorithms since they in a precise sense can be regarded as NP hard problems with minimum time complexity. Indeed, with the help of these languages we relate all of the above problems to the exponential time hypothesis (ETH) in several different ways. (c) 2021 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

    Download full text (pdf)
    fulltext
  • 18.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    A New Characterization of Restriction-Closed Hyperclones2020In: 2020 IEEE 50TH INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL 2020), IEEE COMPUTER SOC , 2020, p. 303-308Conference paper (Refereed)
    Abstract [en]

    A hyperoperation is a mapping from a domain to the powerset of the domain. Hyperoperations can be composed together to form new hyperoperations, and the resulting sets are called hyperclones. In this paper we study the lattice of restriction-closed hyperclones over finite domains. Such hyperclones form a natural subclass of hyperclones but have received comparably little attention. We give a complete description of restriction-closed hyperclones, relative to the clone lattice, and also outline some important open questions to resolve when studying hyperclones over partially defined operations.

  • 19.
    Lagerkvist, Victor
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Wahlström, Magnus
    Royal Holloway, University of London, Egham Hill, Egham, Great Britain.
    Sparsification of SAT and CSP problems via tractable extensions2020In: ACM Transactions on Computation Theory, ISSN 1942-3454, E-ISSN 1942-3462, Vol. 12, no 2, article id 13Article in journal (Refereed)
    Abstract [en]

    Unlike polynomial kernelization in general, for which many non-trivial results and methods exist, only few non-trival algorithms are known for polynomial-time sparsification. Furthermore, excepting problems on restricted inputs (such as graph problems on planar graphs), most such results rely upon encoding the instance as a system of bounded-degree polynomial equations. In particular, for satisfiability (SAT) problems with a fixed constraint language Γ, every previously known result is captured by this approach; for several such problems, this is known to be tight. In this work, we investigate the limits of this approach—in particular, does it really cover all cases of non-trivial polynomial-time sparsification?

    We generalize the method using tools from the algebraic approach to constraint satisfaction problems (CSP). Every constraint that can be modelled via a system of linear equations, over some finite field F, also admits a finite domain extension to a tractable CSP with a Maltsev polymorphism; using known algorithms for Maltsev languages, we can show that every problem of the latter type admits a “basis” of O(n) constraints, which implies a linear sparsification for the original problem. This generalization appears to be strict; other special cases include constraints modelled via group equations over some finite group G. For sparsifications of polynomial but super-linear size, we consider two extensions of this. Most directly, we can capture systems of bounded-degree polynomial equations in a “lift-and-project” manner, by finding Maltsev extensions for constraints over c-tuples of variables, for a basis with O(nc) constraints. Additionally, we may use extensions with k-edge polymorphisms instead of requiring a Maltsev polymorphism.

    We also investigate characterizations of when such extensions exist. We give an infinite sequence of partial polymorphisms φ1, φ2, …which characterizes whether a language Γ has a Maltsev extension (of possibly infinite domain). In the complementary direction of proving lower bounds on kernelizability, we prove that for any language not preserved by φ1, the corresponding SAT problem does not admit a kernel of size O(n2−ε) for any ε > 0 unless the polynomial hierarchy collapses.

    Download full text (pdf)
    fulltext
  • 20.
    Couceiro, Miguel
    et al.
    Univ Lorraine, France.
    Haddad, Lucien
    Royal Mil Coll Canada, Canada.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A Survey2019In: 2019 IEEE 49TH INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL), IEEE , 2019, p. 170-175Conference paper (Refereed)
    Abstract [en]

    Constraint satisfaction problems (CSPs) are combinatorial problems with strong ties to universal algebra and clone theory. The recently proved CSP dichotomy theorem states that finite-domain CSPs are always either tractable or NP-complete. However, among the intractable cases there is a seemingly large variance in complexity, which cannot be explained by the classical algebraic approach using polymorphisms. In this contribution we will survey an alternative approach based on partial polymorphisms, which is useful for studying the fine-grained complexity of NP-complete CSPs. Moreover, we will state some challenging open problems in the research field.

  • 21.
    Lagerkvist, Victor
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Nordh, Gustav
    Independent researcher.
    On the strength of uniqueness quantification in primitive positive formulas2019In: Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019Conference paper (Refereed)
  • 22.
    Lagerkvist, Victor
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Roy, Biman
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    The Inclusion Structure of Boolean Weak Bases2019In: 2019 IEEE 49TH INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL), IEEE , 2019, p. 31-36Conference paper (Refereed)
    Abstract [en]

    Strong partial clones are composition closed sets of partial operations containing all partial projections, characterizable as partial polymorphisms of sets of relations Gamma (pPol(Gamma)). 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(Gamma(w)), where Gamma(w) 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 paper we completely describe the inclusion structure between pPol(Gamma(w)), pPol(Delta(w)) for all Boolean weak bases Gamma(w), and Delta(w.)

  • 23.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Why are CSPs based on partition schemes computationally hard?2018In: Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018Conference paper (Refereed)
  • 24.
    Lagerkvist, Victor
    et al.
    Institut f¨ur Algebra, TU Dresden, Dresden, Germany.
    Roy, Biman
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    A dichotomy theorem for the inverse satisfiability problem2017In: Proceedings ofthe 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017Conference paper (Refereed)
  • 25.
    Lagerkvist, Victor
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Wahlström, Magnus
    Department of Computer Science, Royal Holloway, University of London, London, Great Britain.
    Kernelization of Constraint Satisfaction Problems: A Study Through Universal Algebra2017Conference paper (Refereed)
    Abstract [en]

    A kernelization algorithm for a computational problem is a procedure which compresses an instance into an equivalent instance whose size is bounded with respect to a complexity parameter. For the Boolean satisfiability problem (SAT), and the constraint satisfaction problem (CSP), there exist many results concerning upper and lower bounds for kernelizability of specific problems, but it is safe to say that we lack general methods to determine whether a given SAT problem admits a kernel of a particular size. This could be contrasted to the currently flourishing research program of determining the classical complexity of finite-domain CSP problems, where almost all non-trivial tractable classes have been identified with the help of algebraic properties. In this paper, we take an algebraic approach to the problem of characterizing the kernelization limits of NP-hard SAT and CSP problems, parameterized by the number of variables. Our main focus is on problems admitting linear kernels, as has, somewhat surprisingly, previously been shown to exist. We show that a CSP problem has a kernel with O(n) constraints if it can be embedded (via a domain extension) into a CSP problem which is preserved by a Maltsev operation. We also study extensions of this towards SAT and CSP problems with kernels with O(nc) constraints, c >1, based on embeddings into CSP problems preserved by a k-edge operation, k≤ c+ 1. These results follow via a variant of the celebrated few subpowers algorithm. In the complementary direction, we give indication that the Maltsev condition might be a complete characterization of SAT problems with linear kernels, by showing that an algebraic condition that is shared by all problems with a Maltsev embedding is also necessary for the existence of a linear kernel unless NP ⊆ co-NP/poly.

  • 26.
    Lagerkvist, Victor
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Roy, Biman
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    On the Interval of Boolean Strong Partial Clones Containing Only Projections as Total Operations2017Conference paper (Refereed)
  • 27.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Institut für Algebra, TU Dresden, Dresden, Germany.
    Nordh, Gustav
    Kvarnvägen 6, Hällekis, Sweden.
    Zanuttini, Bruno
    GREYC, Normandie Université, UNICAEN, CNRS, ENSICAEN, France.
    Strong partial clones and the time complexity of SAT problems2017In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 84, p. 52-78Article in journal (Refereed)
    Abstract [en]

    Improving exact exponential-time algorithms for NP-complete problems is an expanding research area. Unfortunately, general methods for comparing the complexity of such problems are sorely lacking. In this article we study the complexity of SAT(S) with reductions increasing the amount of variables by a constant (CV-reductions) or a constant factor (LV-reductions). Using clone theory we obtain a partial order ≤ on languages such that SAT(S) is CV-reducible to SAT(S′) if S≤S′. With this ordering we identify the computationally easiest NP-complete SAT(S) problem (SAT({R})), which is strictly easier than 1-in-3-SAT. We determine many other languages in ≤ and bound their complexity in relation to SAT({R}). Using LV-reductions we prove that the exponential-time hypothesis is false if and only if all SAT(S) problems are subexponential. This is extended to cover degree-bounded SAT(S) problems. Hence, using clone theory, we obtain a solid understanding of the complexity of SAT(S) with CV- and LV-reductions.

    Download full text (pdf)
    fulltext
  • 28.
    Lagerkvist, Victor
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Wahlström, Magnus
    Royal Holloway University of London, England.
    The power of primitive positive definitions with polynomially many variables2017In: Journal of logic and computation (Print), ISSN 0955-792X, E-ISSN 1465-363X, Vol. 27, no 5, p. 1465-1488Article in journal (Refereed)
    Abstract [en]

    Two well-studied closure operators for relations are based on existentially quantified conjunctive formulas, primitive positive (p.p.) definitions, and primitive positive formulas without existential quantification, quantifier-free primitive positive definitions (q.f.p.p.) definitions. Sets of relations closed under p.p. definitions are known as co-clones and sets of relations closed under q.f.p.p. definitions as weak partial co-clones. The latter do however have limited expressivity, and the corresponding lattice of strong partial clones is of uncountably infinite cardinality even for the Boolean domain. Hence, it is reasonable to consider the expressiveness of p.p. definitions where only a small number of existentially quantified variables are allowed. In this article, we consider p.p. definitions allowing only polynomially many existentially quantified variables, and say that a co-clone closed under such definitions is polynomially closed, and otherwise superpolynomially closed. We investigate properties of polynomially closed co-clones and prove that if the corresponding clone contains a k-ary near-unanimity operation for k amp;gt;= 3, then the co-clone is polynomially closed, and if the clone does not contain a k-edge operation for any k amp;gt;= 2, then the co-clone is superpolynomially closed. For the Boolean domain we strengthen these results and prove a complete dichotomy theorem separating polynomially closed co-clones from superpolynomially closed co-clones. Using these results, we then proceed to investigate properties of strong partial clones corresponding to superpolynomially closed co-clones. We prove that if Gamma is a finite set of relations over an arbitrary finite domain such that the clone corresponding to Gamma is essentially unary, then the strong partial clone corresponding to Gamma is of infinite order and cannot be generated by a finite set of partial functions.

    Download full text (pdf)
    fulltext
  • 29.
    Lagerkvist, Victor
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Roy, Biman
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT2016Conference paper (Refereed)
  • 30. Order onlineBuy this publication >>
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Strong Partial Clones and the Complexity of Constraint Satisfaction Problems: Limitations and Applications2016Doctoral thesis, monograph (Other academic)
    Abstract [en]

    In this thesis we study the worst-case time complexity of the constraint satisfaction problem parameterized by a constraint language (CSP(S)), which is the problem of determining whether a conjunctive formula over S has a model. To study the complexity of CSP(S) we borrow methods from universal algebra. In particular, we consider algebras of partial functions, called strong partial clones. This algebraic approach allows us to obtain a more nuanced view of the complexity CSP(S) than possible with algebras of total functions, clones.

    The results of this thesis is split into two main parts. In the first part we investigate properties of strong partial clones, beginning with a classification of weak bases for all Boolean relational clones. Weak bases are constraint languages where the corresponding strong partial clones in a certain sense are extraordinarily large, and they provide a rich amount of information regarding the complexity of the corresponding CSP problems. We then proceed by classifying the Boolean relational clones according to whether it is possible to represent every relation by a conjunctive, logical formula over the weak base without needing more than a polynomial number of existentially quantified variables. A relational clone satisfying this condition is called polynomially closed and we show that this property has a close relationship with the concept of few subpowers. Using this classification we prove that a strong partial clone is of infinite order if (1) the total functions in the strong partial clone are essentially unary and (2) the corresponding constraint language is finite. Despite this, we prove that these strong partial clones can be succinctly represented with finite sets of partial functions, bounded bases, by considering stronger notions of closure than functional composition.

    In the second part of this thesis we apply the theory developed in the first part. We begin by studying the complexity of CSP(S) where S is a Boolean constraint language, the generalised satisfiability problem (SAT(S)). Using weak bases we prove that there exists a relation R such that SAT({R}) is the easiest NP-complete SAT(S) problem. We rule out the possibility that SAT({R}) is solvable in subexponential time unless a well-known complexity theoretical conjecture, the exponential-time hypothesis, (ETH) is false. We then proceed to study the computational complexity of two optimisation variants of the SAT(S) problem: the maximum ones problem over a Boolean constraint language S (MAX-ONES(S)) and the valued constraint satisfaction problem over a set of Boolean cost functions Δ (VCSP(Δ)). For MAX-ONES(S) we use partial clone theory and prove that MAX-ONES({R}) is the easiest NP-complete MAX-ONES(S) problem. These algebraic techniques do not work for VCSP(Δ), however, where we instead use multimorphisms to prove that MAX-CUT is the easiest NP-complete Boolean VCSP(Δ) problem. Similar to the case of SAT(S) we then rule out the possibility of subexponential algorithms for these problems, unless the ETH is false.

    Download full text (pdf)
    fulltext
    Download (pdf)
    omslag
    Download (jpg)
    presentationsbild
  • 31.
    Lagerkvist, Victor
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Wahlström, Magnus
    Department of Computer Science, Royal Holloway, University of London, Great Britain.
    Zanuttini, Bruno
    GREYC, Normandie Université, UNICAEN, CNRS, ENSICAEN, Franc.
    Bounded Bases of Strong Partial Clones2015In: Multiple-Valued Logic (ISMVL), 2015 IEEE International Symposium on, IEEE , 2015, p. 189-194Conference paper (Refereed)
    Abstract [en]

    Partial clone theory has successfully been applied to study the complexity of the constraint satisfaction problem parameterized by a set of relations (CSP(G)). Lagerkvist & Wahlstroï¿œm (ISMVL 2014) however shows that the partial polymorphisms of G (?P?I(G)) cannot be finitely generated for finite, Boolean G if CSP(G) is NP-hard (assuming P?NP). In this paper we consider stronger closure operators than functional composition which can generate ?P?I(G) from a finite set of partial functions, a bounded base. Determining bounded bases for finite languages provides a complete characterization of their partial polymorphisms and we provide such bases for k-SAT and 1-in-k-SAT.

  • 32.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Nordh, Gustav
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Constructing NP-intermediate problems by blowing holes with parameters of various properties2015In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 581, p. 67-82Article in journal (Refereed)
    Abstract [en]

    The search for natural NP-intermediate problems is one of the holy grails within computational complexity. Ladners original diagonalization technique for generating NP-intermediate problems, blowing holes, has a serious shortcoming: it creates problems with a highly artificial structure by arbitrarily removing certain problem instances. In this article we limit this problem by generalizing Ladners method to use parameters with various characteristics. This allows one to define more fine-grained parameters, resulting in NP-intermediate problems where we only blow holes in a controlled subset of the problem. We begin by fully characterizing the problems that admit NP-intermediate subproblems for a broad and natural class of parameterizations, and extend the result further such that structural CSP restrictions based on parameters that are hard to compute (such as tree-width) are covered, thereby generalizing a result by Grohe. For studying certain classes of problems, including CSPs parameterized by constraint languages, we consider more powerful parameterizations. First, we identify a new method for obtaining constraint languages Gamma such that CSP(Gamma) are NP-intermediate. The sets Gamma can have very different properties compared to previous constructions (by, for instance, Bodirsky and Grohe) and provides insights into the algebraic approach for studying the complexity of infinite-domain CSPs. Second, we prove that the propositional abduction problem parameterized by constraint languages admits NP-intermediate problems. This settles an open question posed by Nordh and Zanuttini. (C) 2015 Elsevier B.V. All rights reserved.

    Download full text (pdf)
    fulltext
  • 33.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem2015In: MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2015, PT I, SPRINGER-VERLAG BERLIN , 2015, Vol. 9234, p. 357-368Conference paper (Refereed)
    Abstract [en]

    The monotone constraint satisfaction problem (MCSP) is the problem of, given an existentially quantified positive formula, decide whether this formula has a model. This problem is a natural generalization of the constraint satisfaction problem, which can be seen as the problem of determining whether a conjunctive formula has a model. In this paper we study the worst-case time complexity, measured with respect to the number of variables, n, of the MCSP problem parameterized by a constraint language Gamma (MCSP(Gamma)). We prove that the complexity of the NP-complete MCSP(G) problems on a given finite domain D falls into exactly vertical bar D vertical bar-1 cases and ranges from O(2(n)) to O(vertical bar D vertical bar(n)). We give strong lower bounds and prove that MCSP(G), for any constraint language Gamma over any finite domain, is solvable in O(vertical bar Dvertical bar n) time, where D- is the domain of the core of Gamma, but not solvable in O(vertical bar Dvertical bar(delta n)) time for any delta < 1, unless the strong exponential-time hypothesis fails. Hence, we obtain a complete understanding of the worst-case time complexity of MCSP(Gamma) for constraint languages over arbitrary finite domains.

  • 34.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Upper and Lower Bounds on the Time Complexity of Infinite-domain CSPs2015In: Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Cork, Ireland, August 31 - September 4, 2015, Proceedings / [ed] Pesant, Gilles, Springer Berlin/Heidelberg, 2015, Vol. 9255, p. 183-199Conference paper (Refereed)
    Abstract [en]

    The constraint satisfaction problem (CSP) is a widely studied problem with numerous applications in computer science. For infinite-domain CSPs, there are many results separating tractable and NP-hard cases while upper bounds on the time complexity of hard cases are virtually unexplored. Hence, we initiate a study of the worst-case time cmplexity of such CSPs. We analyse backtracking algorithms and show that they can be improved by exploiting sparsification. We present even faster algorithms based on enumerating finite structures. Last, we prove non-trivial lower bounds applicable to many interesting CSPs, under the assumption that the strong exponential-time hypothesis is true.

  • 35.
    Lagerkvist, Victor
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Wahlström, Magnus
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology. Univ London, Dept Comp Sci, London WC1E 7HU, England.
    Polynomially Closed Co-clones2014In: 2014 IEEE 44TH INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL 2014), IEEE Computer Society, 2014, p. 85-90Conference paper (Refereed)
    Abstract [en]

    Two well-studied closure operators for relations are based on primitive positive (p.p.) definitions and quantifier free p.p. definitions. The latter do however have limited expressiveness and the corresponding lattice of strong partial clones is uncountable. We consider implementations allowing polynomially many existentially quantified variables and obtain a dichotomy for co-clones where such implementations are enough to implement any relation and prove (1) that all remaining coclones contain relations requiring a superpolynomial amount of quantified variables and (2) that the strong partial clones corresponding to two of these co-clones are of infinite order whenever the set of invariant relations can be finitely generated.

  • 36.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Schmidt, Johannes
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Uppman, Hannes
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis2014In: Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II / [ed] Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik, Springer Berlin/Heidelberg, 2014, p. 408-419Conference paper (Refereed)
    Abstract [en]

    Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Recent algebraic techniques introduced by Jonsson et al. (SODA 2013) show that the time complexity of the parameterized SAT(·) problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation R such that SAT(R) can be solved at least as fast as any other NP-hard SAT(·) problem. In this paper we extend this method and show that such languages also exist for the max ones problem (Max-Ones(Γ)) and the Boolean valued constraint satisfaction problem over finite-valued constraint languages (VCSP(Δ)). With the help of these languages we relate Max-Ones and VCSP to the exponential time hypothesis in several different ways.

    Download full text (pdf)
    fulltext
  • 37.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Weak bases of Boolean co-clones2014In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 114, no 9, p. 462-468Article in journal (Refereed)
    Abstract [en]

    Universal algebra has proven to be a useful tool in the study of constraint satisfaction problems (CSP) since the complexity, up to logspace reductions, is determined by the clone of the constraint language. But two CSPs corresponding to the same clone may still differ substantially with respect to worst-case time complexity, which makes clones ill-suited when comparing running times of CSP problems. In this article we instead consider an algebra where each clone splits into an interval of strong partial clones such that a strong partial clone corresponds to the CSPs that are solvable within the same O(c(n)) bound. We investigate these intervals and give relational descriptions, weak bases; of the largest elements. They have a highly regular form and are in many cases easily relatable to the smallest members in the intervals, which suggests that the lattice of strong partial clones has a simpler structure than the lattice of partial clones.

    Download full text (pdf)
    fulltext
  • 38.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Nordh, Gustav
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction2013In: Principles and Practice of Constraint Programming / [ed] Christian Schulte, Springer Berlin/Heidelberg, 2013, p. 398-414Conference paper (Refereed)
    Abstract [en]

    We consider methods for constructing NP-intermediate problems under the assumption that P ≠ NP. We generalize Ladner’s original method for obtaining NP-intermediate problems by using parameters with various characteristics. In particular, this generalization allows us to obtain new insights concerning the complexity of CSP problems. We begin by fully characterizing the problems that admit NP-intermediate subproblems for a broad and natural class of parameterizations, and extend the result further such that structural CSP restrictions based on parameters that are hard to compute (such as tree-width) are covered. Hereby we generalize a result by Grohe on width parameters and NP-intermediate problems. For studying certain classes of problems, including CSPs parameterized by constraint languages, we consider more powerful parameterizations. First, we identify a new method for obtaining constraint languages Γ such that CSP(Γ) are NP-intermediate. The sets Γ can have very different properties compared to previous constructions (by, for instance, Bodirsky & Grohe) and provides insights into the algebraic approach for studying the complexity of infinite-domain CSPs. Second, we prove that the propositional abduction problem parameterized by constraint languages admits NP-intermediate problems. This settles an open question posed by Nordh & Zanuttini.

  • 39.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Lagerkvist, Victor
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Nordh, Gustav
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Zanuttini, Bruno
    Université de Caen Basse-Normandie, France.
    Complexity of SAT problems, Clone Theory and the Exponential Time Hypothesis2013In: SODA-2013, SIAM , 2013, p. 1264-1277Conference paper (Refereed)
1 - 39 of 39
CiteExportLink to result list
Permanent 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