Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting

DOI10.1145/3014587zbMath1446.68073arXiv1507.02479OpenAlexW2952150057MaRDI QIDQ4962659

Stefan Szeider, Robert Ganian, M. S. Ramanujan

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.02479

zbMATH Keywords

countingconstraint satisfactionbackdoor setsconstraint languagesislands of tractability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (10)

Faster FPT algorithms for deletion to pairs of graph classes ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes ⋮ Deletion to scattered graph classes. I: Case of finite number of graph classes ⋮ SAT backdoors: depth beats size ⋮ CSP beyond tractable constraint languages ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Backdoors to planning ⋮ Computational Short Cuts in Infinite Domain Constraint Satisfaction

This page was built for publication: Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting