Publications | Victor Lagerkvist

Preprints

2025

The Richness of CSP Non-redundancy

J. Brakensiek, V. Guruswami, B. M. P. Jansen , and 2 more authors

CoRR, 2025

@article{lagerkvist2025e,
  author = {Brakensiek, J. and Guruswami, V. and Jansen, B. M. P. and Lagerkvist, V. and Wahlstr{\"{o}}m, M.},
  title = {The Richness of {CSP} Non-redundancy},
  journal = {CoRR},
  volume = {abs/2507.07942},
  year = {2025},
  url = {https://doi.org/10.48550/arXiv.2507.07942},
  doi = {10.48550/ARXIV.2507.07942},
  eprinttype = {arXiv},
  eprint = {2507.07942},
  timestamp = {Tue, 12 Aug 2025 21:29:42 +0200},
  biburl = {https://dblp.org/rec/journals/corr/abs-2507-07942.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

Journal and Conference Papers

2026

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings

A. Baril, M. Couceiro, and V. Lagerkvist

Theory of Computing Systems, 2026

Bib PDF

@article{lagerkvist2025d,
  author = {Baril, A. and Couceiro, M. and Lagerkvist, V.},
  title = {Improved Bounds for Twin-Width Parameter Variants with Algorithmic
                    Applications to Counting Graph Colorings},
  journal = {Theory of Computing Systems},
  year = {2026},
  volume = {70},
  issue = {1},
  pages = {12},
  doi = {10.1007/s00224-025-10233-y},
}

Maximum Satisfiability of Simple Temporal Problems

J. Fichte, J. Groven, V. Lagerkvist , and 2 more authors

In Proceedings of the 35th International Joint Conference on Artificial Intelligence (IJCAI-2026) , 2026

To appear

Bib

@inproceedings{lagerkvist2026f,
  title = {Maximum Satisfiability of Simple Temporal Problems},
  author = {Fichte, J. and Groven, J. and Lagerkvist, V. and Jonsson, P. and de Vlas, J. M.},
  year = {2026},
  booktitle = {Proceedings of the 35th International Joint Conference on Artificial Intelligence ({IJCAI}-2026)},
  publisher = {ijcai.org},
  note = {To appear},
}

Representative Sets in Propositional Abduction

J. Schmidt, M. Maizia, V. Lagerkvist , and 1 more author

In Proceedings of the 42nd International Conference on Logic Programming (Technical Communications, ICLP-2026) , 2026

To appear

Bib

@inproceedings{lagerkvist2026e,
  author = {Schmidt, J. and Maizia, M. and Lagerkvist, V. and Fichte, J.},
  title = {Representative Sets in Propositional Abduction},
  booktitle = {Proceedings of the 42nd International Conference on Logic Programming (Technical Communications, {ICLP}-2026)},
  year = {2026},
  note = {To appear},
}

Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach

L. Eriksson, V. Lagerkvist, S. Ordyniak , and 3 more authors

In Proceedings of the 23rd International Conference on Principles of Knowledge Representation and Reasoning (KR-2026) , 2026

To appear

Bib

@inproceedings{eriksson2026d,
  author = {Eriksson, L. and Lagerkvist, V. and Ordyniak, S. and Osipov, G. and Panolan, F. and Rychlicki, M.},
  title = {Clausal Deletion Backdoors for {QBF}: a Parameterized Complexity Approach},
  booktitle = {Proceedings of the 23rd International Conference on Principles of Knowledge Representation and Reasoning ({KR}-2026)},
  year = {2026},
  note = {To appear},
}

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables

P. Jonsson, V. Lagerkvist, J. M. Vlas , and 1 more author

In Proceedings of the 53rd International Colloquium on Automata, Languages, and Programming (ICALP-2026) , 2026

To appear

Bib PDF

@inproceedings{lagerkvist2026c,
  author = {Jonsson, P. and Lagerkvist, V. and de Vlas, J. M. and Wahlstr{\"{o}}m, M.},
  title = {Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables},
  booktitle = {Proceedings of the 53rd International Colloquium on Automata, Languages, and Programming ({ICALP}-2026)},
  year = {2026},
  note = {To appear},
}

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming

L. Eriksson, J. Groven, and V. Lagerkvist

In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI-2026) , 2026

Bib

@inproceedings{lagerkvist2026b,
  author = {Eriksson, L. and Groven, J. and Lagerkvist, V.},
  title = {Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming},
  booktitle = {Proceedings of the 40th AAAI Conference on Artificial Intelligence ({AAAI}-2026)},
  publisher = {{AAAI} Press},
  year = {2026},
  pages = {14287--14294},
}

New perspectives on semiring applications to dynamic programming

A. Baril, M. Couceiro, and V. Lagerkvist

Discrete Applied Mathematics, 2026

Bib PDF

@article{lagerkvist2026a,
  title = {New perspectives on semiring applications to dynamic programming},
  journal = {Discrete Applied Mathematics},
  volume = {383},
  pages = {243-279},
  year = {2026},
  issn = {0166-218X},
  doi = {https://doi.org/10.1016/j.dam.2025.12.035},
  url = {https://www.sciencedirect.com/science/article/pii/S0166218X25007462},
  author = {Baril, A. and Couceiro, M. and Lagerkvist, V.},
  keywords = {Semiring, Dynamic programming, Fixed parameter tractability, Constraint satisfaction problems, Connected dominating set},
}

2025

Complexity of Faceted Explanations in Propositional Abduction

J. Schmidt, M. Maizia, V. Lagerkvist , and 1 more author

Theory and Practice of Logic Programming, 2025

Bib PDF

@article{lagerkvist2025c,
  title = {Complexity of Faceted Explanations in Propositional Abduction},
  volume = {25},
  doi = {10.1017/S1471068425100215},
  number = {4},
  journal = {Theory and Practice of Logic Programming},
  author = {Schmidt, J. and Maizia, M. and Lagerkvist, V. and Fichte, J.},
  year = {2025},
  pages = {775–793},
}

A Fine-Grained Complexity View on Propositional Abduction – Algorithms and Lower Bounds

V. Lagerkvist, M. Maizia, and J. Schmidt

In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI-2025) , 2025

Bib PDF

@inproceedings{lagerkvist2025b,
  title = {A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds},
  author = {Lagerkvist, V. and Maizia, M. and Schmidt, J.},
  year = {2025},
  booktitle = {Proceedings of the 34th International Joint Conference on
                 Artificial Intelligence ({IJCAI}-2025)},
  publisher = {ijcai.org},
}

Facets in Argumentation: A Formal Approach to Argument Significance

J. Fichte, N. Fröhlich, M. Hecher , and 4 more authors

In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI-2025) , 2025

Bib PDF

@inproceedings{lagerkvist2025a,
  title = {Facets in Argumentation: A Formal Approach to Argument Significance},
  author = {Fichte, J. and Fr\"ohlich, N. and Hecher, M. and Lagerkvist, V. and Mahmood, Y. and Meier, A. and Persson, J.},
  year = {2025},
  booktitle = {Proceedings of the 34th International Joint Conference on
                 Artificial Intelligence ({IJCAI}-2025)},
  publisher = {ijcai.org},
}

2024

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzazewski Conjecture

B. Ambroise, M. Couceiro, and V. Lagerkvist

Journal of Multiple-Valued Logic and Soft Computing, 2024

Bib PDF

@article{lagerkvist2024c,
  author = {Ambroise, B. and Couceiro, M. and Lagerkvist, V.},
  title = {The Fine-Grained Complexity of Graph Homomorphism Problems: Towards
                    the Okrasa and Rzazewski Conjecture},
  journal = {Journal of Multiple-Valued Logic and Soft Computing},
  publisher = {Old City Publishing},
  year = {2024},
}

CSPs with Few Alien Constraints

Peter Jonsson, V. Lagerkvist, and George Osipov

In Proceedings of the 30th International Conference on Principles and Practice of Constraint Programming (CP-2024) , 2024

Bib PDF

@inproceedings{lagerkvist2024b,
  author = {Jonsson, Peter and Lagerkvist, V. and Osipov, George},
  title = {CSPs with Few Alien Constraints},
  booktitle = {Proceedings of the 30th International Conference on Principles and Practice of Constraint
                    Programming ({CP}-2024)},
  series = {LIPIcs},
  volume = {307},
  pages = {15:1--15:17},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2024},
  doi = {10.4230/LIPICS.CP.2024.15},
}

Solving Quantified Boolean Formulas with Few Existential Variables

L. Eriksson, V. Lagerkvist, G. Osipov , and 3 more authors

In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI-2024) , 2024

Bib PDF

@inproceedings{lagerkvist2024a,
  author = {Eriksson, L. and Lagerkvist, V. and Osipov, G. and Ordyniak, S. and Panolan, F. and Rychlicki, M.},
  title = {Solving Quantified {B}oolean Formulas with Few Existential Variables},
  booktitle = {Proceedings of the 33rd International Joint Conference on
                 Artificial Intelligence ({IJCAI}-2024)},
  publisher = {ijcai.org},
  year = {2024},
}

2023

Improved Algorithms for Allen’s Interval Algebra by Dynamic Programming with Sublinear Partitioning

L. Eriksson, and V. Lagerkvist

In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI-2023) , 2023

Bib PDF

@inproceedings{lagerkvist2023a,
  author = {Eriksson, L. and Lagerkvist, V.},
  title = {Improved Algorithms for {A}llen's Interval Algebra by Dynamic Programming with Sublinear Partitioning},
  booktitle = {Proceedings of the 32nd International Joint Conference on
                 Artificial Intelligence ({IJCAI}-2023)},
  publisher = {ijcai.org},
  year = {2023},
  pages = {1919--1926},
}

General Lower Bounds and Improved Algorithms for Infinite-Domain CSPs

P. Jonsson, and V. Lagerkvist

Algorithmica, Aug 2023

Bib PDF

@article{Jonsson2022,
  author = {Jonsson, P. and Lagerkvist, V.},
  title = {General Lower Bounds and Improved Algorithms for Infinite-Domain {CSP}s},
  journal = {Algorithmica},
  year = {2023},
  month = aug,
  day = {11},
  issn = {1432-0541},
  doi = {10.1007/s00453-022-01017-8},
  url = {https://doi.org/10.1007/s00453-022-01017-8},
}

A Fast Algorithm for Consistency Checking Partially Ordered Time

L. Eriksson, and V. Lagerkvist

In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI-2023) , Aug 2023

Bib PDF

@inproceedings{lagerkvist2023b,
  author = {Eriksson, L. and Lagerkvist, V.},
  title = {A Fast Algorithm for Consistency Checking Partially Ordered Time},
  booktitle = {Proceedings of the 32nd International Joint Conference on
                 Artificial Intelligence ({IJCAI}-2023)},
  publisher = {ijcai.org},
  year = {2023},
  pages = {1911--1918},
}

2022

The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems

V. Lagerkvist, and M. Wahlström

ACM Transactions on Computation Theory, Aug 2022

Bib PDF

@article{lagerkvist2022a,
  author = {Lagerkvist, V. and Wahlstr\"{o}m, M.},
  title = {The (Coarse) Fine-Grained Structure of {NP}-Hard {SAT} and {CSP} Problems},
  journal = {ACM Transactions on Computation Theory},
  year = {2022},
  issue_date = {March 2022},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  volume = {14},
  number = {1},
  issn = {1942-3454},
  url = {https://doi.org/10.1145/3492336},
  doi = {10.1145/3492336},
}

Computational Short Cuts in Infinite Domain Constraint Satisfaction

P. Jonsson, V. Lagerkvist, and S. Ordyniak

Journal of Artificial Intelligence Research, Aug 2022

Bib PDF

@article{lagerkvist2022e,
  author = {Jonsson, P. and Lagerkvist, V. and Ordyniak, S.},
  title = {Computational Short Cuts in Infinite Domain Constraint Satisfaction},
  journal = {Journal of Artificial Intelligence Research},
  year = {2022},
  doi = {https://doi.org/10.1613/jair.1.13787},
  volume = {75},
}

A Multivariate Complexity Analysis of Qualitative Reasoning Problems

L. Eriksson, and V. Lagerkvist

In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI-2022) , Aug 2022

Bib PDF

@inproceedings{lagerkvist2022d,
  author = {Eriksson, L. and Lagerkvist, V.},
  title = {A Multivariate Complexity Analysis of Qualitative Reasoning Problems},
  booktitle = {Proceedings of the 31st International Joint Conference on
                 Artificial Intelligence ({IJCAI}-2022)},
  pages = {1804--1810},
  publisher = {ijcai.org},
  year = {2022},
  url = {https://doi.org/10.24963/ijcai.2022/251},
  doi = {10.24963/ijcai.2022/251},
  timestamp = {Wed, 27 Jul 2022 16:43:00 +0200},
  biburl = {https://dblp.org/rec/conf/ijcai/ErikssonL22.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

An Algebraic Approach Towards the Fine-Grained Complexity of Graph Coloring Problems

A. Baril, M. Couceiro, and V. Lagerkvist

In Proceedings of the 52nd International Symposium on Multiple-Valued Logic (ISMVL-2022) , Aug 2022

Bib PDF

@inproceedings{lagerkvist2022c,
  title = {An Algebraic Approach Towards the Fine-Grained Complexity of Graph Coloring Problems},
  author = {Baril, A. and Couceiro, M. and Lagerkvist, V.},
  booktitle = {Proceedings of the 52nd International Symposium on Multiple-Valued Logic ({ISMVL}-2022)},
  publisher = {{IEEE}},
  pages = {94--99},
  year = {2022},
  url = {https://doi.org/10.1109/ISMVL52857.2022.00021},
  doi = {10.1109/ISMVL52857.2022.00021},
  timestamp = {Wed, 29 Jun 2022 17:24:42 +0200},
  biburl = {https://dblp.org/rec/conf/ismvl/BarilCL22.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
}

A Survey on the Fine-grained Complexity of Constraint Satisfaction Problems Based on Partial Polymorphisms

M. Couceiro, L. Haddad, and V. Lagerkvist

Journal of Multiple-Valued Logic and Soft Computing, Aug 2022

Bib PDF

@article{lagerkvist2022b,
  author = {Couceiro, M. and Haddad, L. and Lagerkvist, V.},
  title = {A Survey on the Fine-grained Complexity of Constraint
    Satisfaction Problems Based on Partial Polymorphisms},
  journal = {Journal of Multiple-Valued Logic and Soft Computing},
  volume = {38},
  number = {1-2},
  pages = {115--136},
  publisher = {Old City Publishing},
  year = {2022},
}

C-Maximal Strong Partial Clones and the Inclusion Structure of Boolean Weak Bases

V. Lagerkvist, and B. Roy

Journal of Multiple Valued Logic and Soft Computing, Aug 2022

Bib PDF

@article{lagerkvist2021h,
  author = {Lagerkvist, V. and Roy, B.},
  title = {C-Maximal Strong Partial Clones and the Inclusion Structure of Boolean
                 Weak Bases},
  journal = {Journal of Multiple Valued Logic and Soft Computing},
  volume = {38},
  number = {3-4},
  pages = {333--353},
  year = {2022},
}

2021

Acyclic Orders, Partition Schemes and CSPs: Unified Hardness Proofs and Improved Algorithms

P. Jonsson, V. Lagerkvist, and G. Osipov

Artificial Intelligence, Aug 2021

Bib PDF

@article{lagerkvist2021a,
  author = {Jonsson, P. and Lagerkvist, V. and Osipov, G.},
  title = {Acyclic Orders, Partition Schemes and {CSP}s: Unified Hardness Proofs and Improved Algorithms},
  journal = {Artificial Intelligence},
  year = {2021},
  volume = {296},
  pages = {103505},
  issn = {0004-3702},
}

Complexity of Inverse Constraint Problems and a Dichotomy for the Inverse Satisfiability Problem

V. Lagerkvist, and B. Roy

Journal of Computer and System Sciences, Aug 2021

Bib PDF

@article{lagerkvist2020e,
  title = {Complexity of Inverse Constraint Problems and a Dichotomy for the Inverse Satisfiability Problem},
  journal = {Journal of Computer and System Sciences},
  year = {2021},
  volume = {117},
  pages = {23-39},
  author = {Lagerkvist, V. and Roy, B.},
}

Fine-Grained Time Complexity of Constraint Satisfaction Problems

P. Jonsson, V. Lagerkvist, and B. Roy

ACM Transactions on Computation Theory, Aug 2021

Bib PDF

@article{lagerkvist2020f,
  author = {Jonsson, P. and Lagerkvist, V. and Roy, B.},
  title = {Fine-Grained Time Complexity of Constraint Satisfaction Problems},
  journal = {ACM Transactions on Computation Theory},
  publisher = {Association for Computing Machinery},
  year = {2021},
  volume = {13},
  number = {1},
  articleno = {2},
  numpages = {32},
}

Improved Algorithms for Allen’s Interval Algebra: a Dynamic Programming Approach

L. Eriksson, and V. Lagerkvist

In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI-2021) , Aug 2021

Bib PDF

@inproceedings{lagerkvist2021b,
  author = {Eriksson, L. and Lagerkvist, V.},
  title = {Improved Algorithms for {A}llen's Interval Algebra: a Dynamic Programming Approach},
  booktitle = {Proceedings of the 30th International Joint Conference on Artificial Intelligence ({IJCAI}-2021)},
  year = {2021},
  pages = {1873--1879},
  publisher = {ijcai.org},
}

Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors

P. Jonsson, V. Lagerkvist, and S. Ordyniak

In Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming (CP-2021) , Aug 2021

Bib PDF

@inproceedings{lagerkvist2021f,
  author = {Jonsson, P. and Lagerkvist, V. and Ordyniak, S.},
  title = {Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors},
  booktitle = {Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming ({CP-2021})},
  year = {2021},
  series = {Lecture Notes in Computer Science},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  volume = {210},
  pages = {32:1--32:20},
}

The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems

P. Jonsson, V. Lagerkvist, J. Schmidt , and 1 more author

Theoretical Computer Science, Aug 2021

Bib PDF

@article{lagerkvist2021g,
  title = {The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems},
  journal = {Theoretical Computer Science},
  volume = {892},
  pages = {1--24},
  year = {2021},
  issn = {0304-3975},
  author = {Jonsson, P. and Lagerkvist, V. and Schmidt, J. and Uppman, H.},
}

2020

Sparsification of SAT and CSP Problems via Tractable Extensions

V. Lagerkvist, and M. Wahlström

ACM Transactions on Computation Theory, Aug 2020

Bib PDF

@article{lagerkvist2020b,
  author = {Lagerkvist, V. and Wahlstr\"om, M.},
  title = {Sparsification of {SAT} and {CSP} Problems via Tractable Extensions},
  journal = {ACM Transactions on Computation Theory},
  publisher = {Association for Computing Machinery},
  year = {2020},
  articleno = {13},
  numpages = {29},
  volume = {12},
  number = {2},
  address = {New York, NY, USA},
  issn = {1942-3454},
}

A New Characterization of Restriction-Closed Hyperclones

V. Lagerkvist

In Proceedings of the 50th International Symposium on Multiple-Valued Logic (ISMVL-2020) , Aug 2020

Bib PDF

@inproceedings{lagerkvist2020a,
  author = {Lagerkvist, V.},
  title = {A New Characterization of Restriction-Closed Hyperclones},
  booktitle = {Proceedings of the 50th International Symposium on Multiple-Valued Logic ({ISMVL}-2020)},
  publisher = {{IEEE} Computer Society},
  year = {2020},
  pages = {303-308},
  doi = {10.1109/ISMVL49045.2020.00063},
}

Lower Bounds and Faster Algorithms for Equality Constraints

P. Jonsson, and V. Lagerkvist

In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI-2020) , Aug 2020

Bib PDF

@inproceedings{lagerkvist2020c,
  author = {Jonsson, P. and Lagerkvist, V.},
  title = {Lower Bounds and Faster Algorithms for Equality Constraints},
  booktitle = {Proceedings of the 29th International Joint Conference on Artificial Intelligence ({IJCAI}-2020)},
  year = {2020},
  pages = {1784--1790},
}

2019

The Inclusion Structure of Boolean Weak Bases

V. Lagerkvist, and B. Roy

In Proceedings of the 49th International Symposium on Multiple-Valued Logic (ISMVL-2019) , Aug 2019

Bib PDF

@inproceedings{lagerkvist2019b,
  author = {Lagerkvist, V. and Roy, B.},
  title = {The Inclusion Structure of {B}oolean Weak Bases},
  booktitle = {Proceedings of the 49th International Symposium on Multiple-Valued Logic ({ISMVL}-2019)},
  publisher = {{IEEE} Computer Society},
  year = {2019},
  pages = {31--36},
}

Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A Survey

M. Couceiro, L. Haddad, and V. Lagerkvist

In Proceedings of the 49th International Symposium on Multiple-Valued Logic (ISMVL-2019) , Aug 2019

Bib PDF

@inproceedings{lagerkvist2019a,
  author = {Couceiro, M. and Haddad, L. and Lagerkvist, V.},
  title = {Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A Survey},
  booktitle = {Proceedings of the 49th International Symposium on Multiple-Valued Logic ({ISMVL}-2019)},
  publisher = {{IEEE} Computer Society},
  year = {2019},
  pages = {170-175},
}

On the Strength of Uniqueness Quantification in Primitive Positive Formulas

V. Lagerkvist, and G. Nordh

In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS-2019) , Aug 2019

Bib PDF

@inproceedings{lagerkvist2019,
  author = {Lagerkvist, V. and Nordh, G.},
  title = {On the Strength of Uniqueness Quantification in Primitive Positive Formulas},
  booktitle = {Proceedings of the 44th International Symposium on Mathematical Foundations of Computer
                 Science ({MFCS}-2019)},
  series = {LIPIcs},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  volume = {138},
  pages = {36:1--36:15},
  year = {2019},
}

2018

Why are CSPs Based on Partition Schemes Computationally Hard?

P. Jonsson, and V. Lagerkvist

In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS-2018) , Aug 2018

Bib PDF

@inproceedings{DBLP:conf/mfcs/JonssonL18,
  author = {Jonsson, P. and Lagerkvist, V.},
  title = {Why are {CSP}s Based on Partition Schemes Computationally Hard?},
  booktitle = {Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer
                 Science ({MFCS}-2018)},
  series = {LIPIcs},
  volume = {117},
  pages = {43:1--43:15},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year = {2018},
}

2017

An initial study of time complexity in infinite-domain constraint satisfaction

P. Jonsson, and V. Lagerkvist

Artificial Intelligence, Aug 2017

Bib PDF

@article{lagerkvist2017d,
  author = {Jonsson, P. and Lagerkvist, V.},
  title = {An initial study of time complexity in infinite-domain constraint
                 satisfaction},
  journal = {Artificial Intelligence},
  volume = {245},
  pages = {115--133},
  year = {2017},
  doi = {10.1016/j.artint.2017.01.005},
  timestamp = {Sat, 27 May 2017 14:24:42 +0200},
  biburl = {http://dblp.uni-trier.de/rec/bib/journals/ai/JonssonL17},
  bibsource = {dblp computer science bibliography, http://dblp.org},
}

A Dichotomy Theorem for the Inverse Satisfiability Problem

V. Lagerkvist, and B. Roy

In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS-2017) , Aug 2017

Bib PDF

@inproceedings{lagerkvist207f,
  author = {Lagerkvist, V. and Roy, B.},
  title = {A Dichotomy Theorem for the Inverse Satisfiability Problem},
  booktitle = {Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science ({FSTTCS}-2017)},
  pages = {39:39--39:14},
  isbn = {978-3-95977-055-2},
  issn = {1868-8969},
  year = {2017},
  volume = {93},
}

Time Complexity of Constraint Satisfaction via Universal Algebra

P. Jonsson, V. Lagerkvist, and B. Roy

In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS-2017) , Aug 2017

Bib PDF

@inproceedings{lagerkvist2017e,
  author = {Jonsson, P. and Lagerkvist, V. and Roy, B.},
  year = {2017},
  pages = {17:1--17:15},
  isbn = {978-3-95977-046-0},
  issn = {1868-8969},
  title = {Time Complexity of Constraint Satisfaction via Universal Algebra},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  booktitle = {Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science ({MFCS}-2017)},
}

The power of primitive positive definitions with polynomially many variables

V. Lagerkvist, and M. Wahlström

Journal of Logic and Computation, Aug 2017

Bib PDF

@article{lagerkvist2017c,
  author = {Lagerkvist, V. and Wahlstr\"om, M.},
  title = {The power of primitive positive definitions with polynomially many variables},
  journal = {Journal of Logic and Computation},
  volume = {27},
  number = {5},
  pages = {1465-1488},
  year = {2017},
  doi = {10.1093/logcom/exw005},
}

On the Interval of Boolean Strong Partial Clones Containing Only Projections as Total Operations

M. Couceiro, L. Haddad, V. Lagerkvist , and 1 more author

In Proceedings of the 47th International Symposium on Multiple-Valued Logic (ISMVL-2017) , Aug 2017

Bib PDF

@inproceedings{lagerkvist2017,
  author = {Couceiro, M. and Haddad, L. and Lagerkvist, V. and Roy, B.},
  title = {On the Interval of {B}oolean Strong Partial Clones Containing Only Projections
                 as Total Operations},
  booktitle = {Proceedings of the 47th International Symposium on Multiple-Valued Logic ({ISMVL}-2017)},
  pages = {88--93},
  publisher = {{IEEE} Computer Society},
  year = {2017},
}

Kernelization of Constraint Satisfaction Problems: A Study Through Universal Algebra

V. Lagerkvist, and M. Wahlström

In Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming (CP-2017) , Aug 2017

Bib PDF

@inproceedings{lagerkvist2017b,
  author = {Lagerkvist, V. and Wahlstr{\"o}m, M.},
  title = {Kernelization of Constraint Satisfaction Problems: A Study Through Universal Algebra},
  booktitle = {Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming ({CP-2017})},
  year = {2017},
  publisher = {Springer International Publishing},
  pages = {157--171},
  isbn = {978-3-319-66158-2},
}

Strong partial clones and the time complexity of SAT problems

P. Jonsson, V. Lagerkvist, G. Nordh , and 1 more author

Journal of Computer and System Sciences, Aug 2017

Bib PDF

@article{jonsson2017,
  title = {Strong partial clones and the time complexity of {SAT} problems },
  journal = {Journal of Computer and System Sciences},
  volume = {84},
  number = {},
  pages = {52 - 78},
  year = {2017},
  note = {},
  issn = {0022-0000},
  author = {Jonsson, P. and Lagerkvist, V. and Nordh, G. and Zanuttini, B.},
}

2016

A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT

V. Lagerkvist, and B. Roy

In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS-2016) , Aug 2016

Bib PDF

@inproceedings{Lagerkvist2016c,
  author = {Lagerkvist, V. and Roy, B.},
  title = {{A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT}},
  booktitle = {Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science ({MFCS}-2016)},
  pages = {64:1--64:14},
  year = {2016},
  volume = {58},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
}

2015

Upper and Lower Bounds on the Time Complexity of Infinite-Domain CSPs

P. Jonsson, and V. Lagerkvist

In Proceedings of the 21st International Conference on Principles and Practice of Constraint Programming (CP-2015) , Aug 2015

Bib PDF

@inproceedings{lagerkvist2015c,
  year = {2015},
  isbn = {978-3-319-23218-8},
  booktitle = {Proceedings of the 21st International Conference on Principles and Practice of Constraint Programming ({CP}-2015)},
  volume = {9255},
  series = {Lecture Notes in Computer Science},
  doi = {10.1007/978-3-319-23219-5_14},
  title = {Upper and Lower Bounds on the Time Complexity of Infinite-Domain {CSP}s},
  publisher = {Springer International Publishing},
  author = {Jonsson, P. and Lagerkvist, V.},
  pages = {183-199},
  language = {English},
}

Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem

V. Lagerkvist

In Proceedings of the Mathematical Foundations of Computer Science 2015 (MFCS-2015) , Aug 2015

Bib PDF

@inproceedings{lagerkvist2015b,
  year = {2015},
  isbn = {978-3-662-48056-4},
  booktitle = {Proceedings of the Mathematical Foundations of Computer Science 2015 ({MFCS}-2015)},
  volume = {9234},
  series = {Lecture Notes in Computer Science},
  doi = {10.1007/978-3-662-48057-1_28},
  title = {Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem},
  publisher = {Springer Berlin Heidelberg},
  author = {Lagerkvist, V.},
  pages = {357-368},
  language = {English},
}

Constructing NP-intermediate Problems by Blowing Holes with Parameters of Various Properties

P. Jonsson, V. Lagerkvist, and G. Nordh

Theoretical Computer Science, May 2015

Bib PDF

@article{jonsson2015,
  author = {Jonsson, P. and Lagerkvist, V. and Nordh, G.},
  title = {Constructing {NP}-intermediate Problems by Blowing Holes with Parameters of Various Properties},
  journal = {Theoretical Computer Science},
  issue_date = {May 2015},
  volume = {581},
  number = {C},
  month = may,
  year = {2015},
  issn = {0304-3975},
  pages = {67--82},
  numpages = {16},
  doi = {10.1016/j.tcs.2015.03.009},
  acmid = {2781227},
  publisher = {Elsevier Science Publishers Ltd.},
  address = {Essex, UK},
}

Bounded Bases of Strong Partial Clones

V. Lagerkvist, M. Wahlström, and B. Zanuttini

In Proceedings of the 45th International Symposium on Multiple-Valued Logic (ISMVL-2015) , Waterloo, Canada, May 2015

Bib PDF

@inproceedings{lagerkvist2015,
  author = {Lagerkvist, V. and Wahlstr{\"{o}}m, M. and Zanuttini, B.},
  title = {Bounded Bases of Strong Partial Clones},
  booktitle = {Proceedings of the 45th International Symposium on Multiple-Valued Logic ({ISMVL}-2015)},
  location = {Waterloo, Canada},
  year = {2015},
  pages = {189--194},
  publisher = {{IEEE} Computer Society},
}

2014

Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis

P. Jonsson, V. Lagerkvist, J. Schmidt , and 1 more author

In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014) , May 2014

Bib PDF

@inproceedings{jonssonetal2014,
  author = {Jonsson, P. and Lagerkvist, V. and Schmidt, J. and Uppman, H.},
  title = {Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis},
  year = {2014},
  pages = {408--419},
  booktitle = {Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014)},
  publisher = {Springer-Verlag},
  address = {Berlin, Heidelberg},
}

Weak bases of Boolean co-clones

V. Lagerkvist

Information Processing Letters, May 2014

Bib PDF

@article{Lagerkvist2014,
  author = {Lagerkvist, V.},
  title = {Weak bases of {B}oolean co-clones},
  journal = {Information Processing Letters},
  volume = {114},
  number = {9},
  year = {2014},
  pages = {462-468},
}

Polynomially Closed Co-Clones

V. Lagerkvist, and M. Wahlström

In Proceedings of the 44th International Symposium on Multiple-Valued Logic (ISMVL-2014) , May 2014

Bib PDF

@inproceedings{lagerkvistwahlstrom2014,
  author = {Lagerkvist, V. and Wahlstr\"om, M.},
  booktitle = {Proceedings of the 44th International Symposium on Multiple-Valued Logic ({ISMVL}-2014)},
  title = {Polynomially Closed Co-Clones},
  year = {2014},
  pages = {85 - 90},
  publisher = {{IEEE} Computer Society},
}

2013

Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis

P. Jonsson, V. Lagerkvist, G. Nordh , and 1 more author

In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2013) , May 2013

Bib PDF

@inproceedings{Jonsson:etal:soda2013,
  author = {Jonsson, P. and Lagerkvist, V. and Nordh, G. and Zanuttini, B.},
  title = {Complexity of {SAT} Problems, Clone Theory and the Exponential
                 Time Hypothesis},
  booktitle = {Proceedings of the 24th Annual {ACM-SIAM} Symposium on Discrete Algorithms ({SODA}-2013)},
  year = {2013},
  pages = {1264-1277},
  ee = {http://knowledgecenter.siam.org/0236-000094/},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  publisher = {{SIAM}},
}

Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction

P. Jonsson, V. Lagerkvist, and G. Nordh

In Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP-2013) , May 2013

Bib PDF

@inproceedings{lagerkvist2013b,
  year = {2013},
  isbn = {978-3-642-40626-3},
  booktitle = {Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming ({CP}-2013)},
  volume = {8124},
  series = {Lecture Notes in Computer Science},
  doi = {10.1007/978-3-642-40627-0_32},
  title = {Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction},
  publisher = {Springer Berlin Heidelberg},
  author = {Jonsson, P. and Lagerkvist, V. and Nordh, G.},
  pages = {398-414},
  language = {English},
}