Counting homomorphisms in plain exponential time

DOI10.4230/LIPICS.ICALP.2020.21MaRDI QIDQ6842556zbMATH OpenFDO

Authors Andrei A. Bulatov, Amineh Dadsetan

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.21

zbMATH Keywords

clique widthgraph homomorphismsplain exponential time

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• Exact algorithms for graph homomorphisms
• Graph classes with and without powers of bounded clique-width
• Graph isomorphism in quasipolynomial time (extended abstract)
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Improved Exact Algorithms for Counting 3- and 4-Colorings
• Kneser's conjecture, chromatic number, and homotopy
• Lower bounds based on the exponential time hypothesis
• New graph classes of bounded clique-width
• New Plain-Exponential Time Classes for Graph Homomorphism
• On the clique-width of graph with few \(P_{4}\)'s
• On the clique-width of some perfect graph classes
• On the complexity of H-coloring
• Strong computational lower bounds via parameterized complexity
• The complexity of counting homomorphisms seen from the other side
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The Time Complexity of Constraint Satisfaction
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Tight lower bounds for the complexity of multicoloring

Cited in

(1)

• Improved bounds for twin-width parameter variants with algorithmic applications to counting graph colorings

This page was built for publication: Counting homomorphisms in plain exponential time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6842556)