scientific article; zbMATH DE number 7561704

DOI10.4230/LIPIcs.MFCS.2019.60zbMath1499.68238arXiv1907.07922MaRDI QIDQ5092423

Andrei A. Bulatov, Stanislav Živný

Publication date: 21 July 2022

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

homomorphismsconstraint satisfactionapproximate counting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Hypertree decompositions and tractable queries
• The complexity of counting homomorphisms seen from the other side
• The complexity of approximating conservative counting CSPs
• Graph minors. III. Planar tree-width
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• An approximation trichotomy for Boolean \#CSP
• Graph minors. V. Excluding a planar graph
• On the complexity of H-coloring
• Parameterized circuit complexity and the \(W\) hierarchy
• Conjunctive-query containment and constraint satisfaction
• The relative complexity of approximate counting problems
• Complexity of generalized satisfiability counting problems
• Parametrized complexity theory.
• Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• Matrix Partitions with Finitely Many Obstructions
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Constraint solving via fractional edge covers
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Complexity of Counting CSP with Complex Weights
• The Parameterized Complexity of Counting Problems
• Fixed-Parameter Tractability and Completeness I: Basic Results
• A Complexity Trichotomy for Approximately Counting List H -Colorings
• When is the evaluation of conjunctive queries tractable?
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of the counting constraint satisfaction problem
• The complexity of satisfiability problems

This page was built for publication: