Combining Treewidth and Backdoors for CSP.

DOI10.4230/LIPIcs.STACS.2017.36zbMath1402.68094arXiv1610.03298OpenAlexW2963805305MaRDI QIDQ4636635

Robert Ganian, Stefan Szeider, M. S. Ramanujan

Publication date: 19 April 2018

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

zbMATH Keywords

constraint satisfactionfixed-parameter tractabilityfixed-parameter algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Related Items (12)

A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ FPT algorithms to compute the elimination distance to bipartite graphs and more ⋮ Solving projected model counting by utilizing treewidth and its limits ⋮ SAT backdoors: depth beats size ⋮ CSP beyond tractable constraint languages ⋮ Backdoor Sets for CSP. ⋮ On the Parameterized Complexity of Clique Elimination Distance ⋮ Backdoors into heterogeneous classes of SAT and CSP ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs

This page was built for publication: Combining Treewidth and Backdoors for CSP.