Catarina Carvalho
From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP
Carvalho, Catarina; Madelaine, Florent R.; Martin, Barnaby
Abstract
Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idem potent polymorphisms of certain digraph classes. Our first results are two algebraic dichotomy, even "gap", theorems. Building on and extending [Martin CP'11], we prove that partially reflexive paths bequeath a set of idem potent polymorphisms whose associated clone algebra has: either the polynomially generated powers property (PGP), or the exponentially generated powers property (EGP). Similarly, we build on [DaMM ICALP'14] to prove that semi complete digraphs have the same property. These gap theorems are further motivated by new evidence that PGP could be the algebraic explanation that a QCSP is in NP even for unbounded alternation. Along the way we also effect a study of a concrete form of PGP known as collapsibility, tying together the algebraic and structural threads from [Chen Sicomp'08], and show that collapsibility is equivalent to its Pi2-restriction. We also give a decision procedure for k-collapsibility from a singleton source of a finite structure (a form of collapsibility which covers all known examples of PGP for finite structures). Finally, we present a new QCSP trichotomy result, for partially reflexive paths with constants. Without constants it is known these QCSPs are either in NL or Pspace-complete [Martin CP'11], but we prove that with constants they attain the three complexities NL, NP-complete and Pspace-complete.
Citation
Carvalho, C., Madelaine, F. R., & Martin, B. (2015). From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP. In Proceedings, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015) : 6-10 July 2015, Kyoto, Japan (462-474). https://doi.org/10.1109/lics.2015.50
Conference Name | 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015 |
---|---|
Conference Location | Kyoto, Japan |
Start Date | Jul 6, 2015 |
End Date | Jul 10, 2015 |
Acceptance Date | Mar 30, 2015 |
Online Publication Date | Aug 3, 2015 |
Publication Date | Aug 3, 2015 |
Deposit Date | Oct 14, 2016 |
Publicly Available Date | Mar 28, 2024 |
Pages | 462-474 |
Series ISSN | 1043-6871 |
Book Title | Proceedings, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015) : 6-10 July 2015, Kyoto, Japan. |
ISBN | 9781479988471 |
DOI | https://doi.org/10.1109/lics.2015.50 |
Files
Accepted Conference Proceeding
(575 Kb)
PDF
Copyright Statement
© 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
You might also like
The lattice and semigroup structure of multipermutations
(2021)
Journal Article
Constraint satisfaction problems for reducts of homogeneous graphs
(2019)
Journal Article
Surjective H-Colouring over reflexive digraphs
(2018)
Journal Article
On the Complexity of the Model Checking Problem
(2018)
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