Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs
From MaRDI portal
Publication:5858645
DOI10.1137/20M1320146MaRDI QIDQ5858645
Karolina Okrasa, Paweł Rzążewski
Publication date: 14 April 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1906.08371
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Complexity of \(C_k\)-coloring in hereditary classes of graphs, List homomorphism: beyond the known boundaries
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- New plain-exponential time classes for graph homomorphism
- The core of a graph
- Graph minors. III. Planar tree-width
- \(H\)-coloring dichotomy revisited
- On the complexity of H-coloring
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- List homomorphisms to reflexive graphs
- S-functions for graphs
- Which problems have strongly exponential complexity?
- House of Graphs: a database of interesting graphs
- List homomorphisms and circular arc graphs
- Counterexamples to Hedetniemi's conjecture
- Deleting vertices to graphs of bounded genus
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Exact algorithm for graph homomorphism and locally injective graph homomorphism
- Nonserial dynamic programming
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Exact algorithms for graph homomorphisms
- The Fine Details of Fast Dynamic Programming over Tree Decompositions
- A New Proof of the H-Coloring Dichotomy
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Strongly Projective Graphs
- Note on projective graphs
- Graph Theory and Probability
- The Kronecker Product of Graphs
- On Cartesian skeletons of graphs
- Set Partitioning via Inclusion-Exclusion
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Complexity of Finding Embeddings in a k-Tree
- Applications of product colouring
- Families of strongly projective graphs
- Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
- Tight Lower Bounds on Graph Embedding Problems
- Bi‐arc graphs and the complexity of list homomorphisms
- Parameterized Algorithms
- The Categorical Product of Graphs
- PRIMITIVE AND IMPRIMITIVE GRAPHS
- Cardinal multiplication of structures with a reflexive relation
- Hedetniemi's conjecture---a survey
- On the complexity of \(k\)-SAT
