Florent Madelaine
Consistency for counting quantifiers
Madelaine, Florent; Martin, Barnaby
Authors
Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor
Contributors
Igor Potapov
Editor
Paul Spirakis
Editor
James Worrell
Editor
Abstract
We apply the algebraic approach for Constraint Satisfaction Problems (CSPs) with counting quantifiers, developed by Bulatov and Hedayaty, for the first time to obtain classifications for computational complexity. We develop the consistency approach for expanding polymorphisms to deduce that, if H has an expanding majority polymorphism, then the corresponding CSP with counting quantifiers is tractable. We elaborate some applications of our result, in particular deriving a complexity classification for partially reflexive graphs endowed with all unary relations. For each such structure, either the corresponding CSP with counting quantifiers is in P, or it is NP-hard.
Citation
Madelaine, F., & Martin, B. (2018). Consistency for counting quantifiers. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK) (11:1-11:13). https://doi.org/10.4230/lipics.mfcs.2018.11
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). |
Start Date | Aug 27, 2018 |
End Date | Aug 31, 2018 |
Acceptance Date | Jun 13, 2018 |
Publication Date | Aug 31, 2018 |
Deposit Date | Jul 12, 2018 |
Publicly Available Date | Jun 27, 2019 |
Volume | 117 |
Pages | 11:1-11:13 |
Series Title | Leibniz International Proceedings in Informatics (LIPIcs) |
Series ISSN | 1868-8969 |
Book Title | 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK). |
DOI | https://doi.org/10.4230/lipics.mfcs.2018.11 |
Public URL | https://durham-repository.worktribe.com/output/1145134 |
Files
Accepted Conference Proceeding
(559 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© B. Martin and F. R. Madelaine; licensed under Creative Commons License CC-BY
Published Conference Proceeding
(465 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
You might also like
Depth lower bounds in Stabbing Planes for combinatorial principles
(2024)
Journal Article
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
(2023)
Presentation / Conference Contribution
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
(2023)
Journal Article
Few induced disjoint paths for H-free graphs
(2022)
Presentation / Conference Contribution
Few induced disjoint paths for H-free graphs
(2022)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search