The fine-grained complexity of graph homomorphism parameterized by clique-width

DOI10.1145/3652514MaRDI QIDQ7023553zbMATH OpenFDO

Authors Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, Kirill Simonov

Publication date 21 February 2025

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3652514

zbMATH Keywords

clique-widthfine-grained complexityhomomorphism

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A new proof of the \(H\)-coloring dichotomy
• Absolute reflexive retracts and absolute bipartite retracts
• Approximating clique-width and branch-width
• Bi‐arc graphs and the complexity of list homomorphisms
• Exact algorithm for graph homomorphism and locally injective graph homomorphism
• Exact algorithms for graph homomorphisms
• Families of strongly projective graphs
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
• Finer tight bounds for coloring on clique-width
• Graph minors. II. Algorithmic aspects of tree-width
• Graph-Theoretic Concepts in Computer Science
• Grundy distinguishes treewidth from pathwidth
• Handbook of product graphs
• scientific article; zbMATH DE number 7228418 (Why is no real title available?)
• scientific article; zbMATH DE number 1151810 (Why is no real title available?)
• scientific article; zbMATH DE number 1775538 (Why is no real title available?)
• scientific article; zbMATH DE number 3445294 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 7651213 (Why is no real title available?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• Lower bounds based on the exponential time hypothesis
• New plain-exponential time classes for graph homomorphism
• Note on projective graphs
• On sparse graphs with given colorings and homomorphisms.
• On the complexity of k-SAT
• On the complexity of H-coloring
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The core of a graph
• Tight lower bounds on graph embedding problems
• Upper bounds to the clique width of graphs
• Which problems have strongly exponential complexity?

Cited in

(2)

• Structural parameterizations for two bounded degree problems revisited
• Kernelization for H-coloring

This page was built for publication: The fine-grained complexity of graph homomorphism parameterized by clique-width

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