liu.seSearch for publications in DiVA
Change search

BETA
Lagerkvist, Viktor
Publications (10 of 10) Show all publications
Lagerkvist, V. (2016). Strong Partial Clones and the Complexity of Constraint Satisfaction Problems: Limitations and Applications. (Doctoral dissertation). Linköping: Linköping University Electronic Press
Open this publication in new window or tab >>Strong Partial Clones and the Complexity of Constraint Satisfaction Problems: Limitations and Applications
2016 (English)Doctoral 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.

Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1733
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-122827 (URN)10.3384/diss.diva-122827 (DOI)978-91-7685-856-1 (ISBN)
Public defence
2016-02-03, Alan Turing, hus E, Campus Valla, Linköpiong, 13:15 (English)
Funder
CUGS (National Graduate School in Computer Science) Available from: 2015-12-15 Created: 2015-11-25 Last updated: 2018-01-10Bibliographically approved
Lagerkvist, V., Wahlström, M. & Zanuttini, B. (2015). Bounded Bases of Strong Partial Clones. In: Multiple-Valued Logic (ISMVL), 2015 IEEE International Symposium on: . Paper presented at 2015 IEEE 45th International Symposium on Multiple-Valued Logic, 18–20 May 2015, Waterloo, Ontario, Canada (pp. 189-194). IEEE
Open this publication in new window or tab >>Bounded Bases of Strong Partial Clones
2015 (English)In: Multiple-Valued Logic (ISMVL), 2015 IEEE International Symposium on, IEEE , 2015, p. 189-194Conference paper, Published 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.

IEEE, 2015
Series
International Symposium on Multiple-Valued Logic. Proceedings, ISSN 0195-623X
Keywords
computational complexity;functions;set theory;G (?P?I(G));bounded base;closure operators;partial functions;partial polymorphisms;strong partial clone;Assistive technology;Cloning;Context;Electronic mail;Lattices;NP-hard problem;Clone theory;constraint satisfaction;partial clone theory
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-123384 (URN)10.1109/ISMVL.2015.33 (DOI)000380463600033 ()978-1-4799-1777-8 (ISBN)
Conference
2015 IEEE 45th International Symposium on Multiple-Valued Logic, 18–20 May 2015, Waterloo, Ontario, Canada
Available from: 2015-12-15 Created: 2015-12-15 Last updated: 2018-01-10Bibliographically approved
Jonsson, P., Lagerkvist, V. & Nordh, G. (2015). Constructing NP-intermediate problems by blowing holes with parameters of various properties. Theoretical Computer Science, 581, 67-82
Open this publication in new window or tab >>Constructing NP-intermediate problems by blowing holes with parameters of various properties
2015 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 581, p. 67-82Article in journal (Refereed) Published
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.

Elsevier, 2015
Keywords
Computational complexity; NP-intermediate problems; Constraint satisfaction problems; Abduction problems
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-118236 (URN)10.1016/j.tcs.2015.03.009 (DOI)000353608700005 ()
Note

Funding Agencies|Swedish Research Council (VR) [621-2012-3239]; National Graduate School in Computer Science (CUGS) [12.02]

Available from: 2015-05-22 Created: 2015-05-22 Last updated: 2018-01-11
Lagerkvist, V. (2015). Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem. In: MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2015, PT I: . Paper presented at 40th International Symposium on Mathematical Foundations of Computer Science (MFCS) (pp. 357-368). SPRINGER-VERLAG BERLIN, 9234
Open this publication in new window or tab >>Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem
2015 (English)In: MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2015, PT I, SPRINGER-VERLAG BERLIN , 2015, Vol. 9234, p. 357-368Conference paper, Published 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 &lt; 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.

Place, publisher, year, edition, pages
SPRINGER-VERLAG BERLIN, 2015
Series
Lecture Notes in Computer Science, ISSN 0302-9743
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-126283 (URN)10.1007/978-3-662-48057-1_28 (DOI)000371025600033 ()978-3-662-48057-1; 978-3-662-48056-4 (ISBN)
Conference
40th International Symposium on Mathematical Foundations of Computer Science (MFCS)
Available from: 2016-03-21 Created: 2016-03-21 Last updated: 2018-01-10
Jonsson, P. & Lagerkvist, V. (2015). Upper and Lower Bounds on the Time Complexity of Infinite-domain CSPs. In: Pesant, Gilles (Ed.), Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Cork, Ireland, August 31 - September 4, 2015, Proceedings: . Paper presented at 21st International Conference on Principles and Practice of Constraint Programming (CP-2015) (pp. 183-199). Springer Berlin/Heidelberg, 9255
Open this publication in new window or tab >>Upper and Lower Bounds on the Time Complexity of Infinite-domain CSPs
2015 (English)In: 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, Published 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.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2015
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 9255
National Category
Computer and Information Sciences Computer Sciences
Identifiers
urn:nbn:se:liu:diva-123120 (URN)10.1007/978-3-319-23219-5_14 (DOI)000364707100014 ()978-3-319-23218-8 (ISBN)
Conference
21st International Conference on Principles and Practice of Constraint Programming (CP-2015)
Available from: 2015-12-04 Created: 2015-12-04 Last updated: 2018-02-20
Lagerkvist, V. & Wahlström, M. (2014). Polynomially Closed Co-clones. In: 2014 IEEE 44TH INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL 2014): . Paper presented at IEEE 44th International Symposium on Multiple-Valued Logic (ISMVL-2014) (pp. 85-90). IEEE Computer Society
Open this publication in new window or tab >>Polynomially Closed Co-clones
2014 (English)In: 2014 IEEE 44TH INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL 2014), IEEE Computer Society, 2014, p. 85-90Conference paper, Published 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.

Place, publisher, year, edition, pages
IEEE Computer Society, 2014
Series
International Symposium on Multiple-Valued Logic, ISSN 0195-623X
National Category
Natural Sciences Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-112915 (URN)10.1109/ISMVL.2014.23 (DOI)000361020700015 ()9781479935369 (ISBN)
Conference
IEEE 44th International Symposium on Multiple-Valued Logic (ISMVL-2014)
Available from: 2014-12-19 Created: 2014-12-19 Last updated: 2018-01-11
Jonsson, P., Lagerkvist, V., Schmidt, J. & Uppman, H. (2014). Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis. In: Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik (Ed.), Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik (Ed.), Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II. Paper presented at 39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014) (pp. 408-419). Springer Berlin/Heidelberg
Open this publication in new window or tab >>Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
2014 (English)In: 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, Published 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.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2014
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 8635
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-112902 (URN)10.1007/978-3-662-44465-8_35 (DOI)000358254600035 ()2-s2.0-84906261436 (Scopus ID)978-3-662-44464-1 (ISBN)978-3-662-44465-8 (ISBN)
Conference
39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014)
Available from: 2014-12-19 Created: 2014-12-19 Last updated: 2018-07-17Bibliographically approved
Lagerkvist, V. (2014). Weak bases of Boolean co-clones. Information Processing Letters, 114(9), 462-468
Open this publication in new window or tab >>Weak bases of Boolean co-clones
2014 (English)In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 114, no 9, p. 462-468Article in journal (Refereed) Published
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.

Elsevier, 2014
Keywords
Computational complexity; Clone theory; Boolean relations; Constraint satisfaction problems
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-108789 (URN)10.1016/j.ipl.2014.03.011 (DOI)000336877100002 ()
Available from: 2014-07-07 Created: 2014-07-06 Last updated: 2017-12-05
Jonsson, P., Lagerkvist, V. & Nordh, G. (2013). Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction. In: Christian Schulte (Ed.), Principles and Practice of Constraint Programming: . Paper presented at 19th International Conference on Principles and Practice of Constraint Programming (CP-2013), Uppsala, Sweden, September 16-20, 2013 (pp. 398-414). Springer Berlin/Heidelberg
Open this publication in new window or tab >>Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction
2013 (English)In: Principles and Practice of Constraint Programming / [ed] Christian Schulte, Springer Berlin/Heidelberg, 2013, p. 398-414Conference paper, Published 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.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 8124
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-102673 (URN)10.1007/978-3-642-40627-0_32 (DOI)000329244000032 ()978-3-642-40626-3 (ISBN)978-3-642-40627-0 (ISBN)
Conference
19th International Conference on Principles and Practice of Constraint Programming (CP-2013), Uppsala, Sweden, September 16-20, 2013
Available from: 2013-12-18 Created: 2013-12-18 Last updated: 2018-02-19Bibliographically approved
Jonsson, P., Lagerkvist, V., Nordh, G. & Zanuttini, B. (2013). Complexity of SAT problems, Clone Theory and the Exponential Time Hypothesis. In: SODA-2013: . Paper presented at 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2013), 6-8 January 3013, New Orleans, Louisiana, USA (pp. 1264-1277). SIAM
Open this publication in new window or tab >>Complexity of SAT problems, Clone Theory and the Exponential Time Hypothesis
2013 (English)In: SODA-2013, SIAM , 2013, p. 1264-1277Conference paper, Published paper (Refereed)
SIAM, 2013
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-102658 (URN)9781627484855 (ISBN)
Conference
24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2013), 6-8 January 3013, New Orleans, Louisiana, USA
Available from: 2013-12-18 Created: 2013-12-18 Last updated: 2018-01-11Bibliographically approved

Search in DiVA

Show all publications