Lower Bounds for the Graph Homomorphism Problem

DOI10.1007/978-3-662-47672-7_39zbMath1440.68102arXiv1502.05447OpenAlexW2169633784WikidataQ60488393 ScholiaQ60488393MaRDI QIDQ3448809

Alexander Golovnev, Ivan Mihajlin, Fedor V. Fomin, Alexander S. Kulikov

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

Testing the Complexity of a Valued CSP Language

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast exact algorithm for \(L(2,1)\)-labeling of graphs
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Exact exponential algorithms.
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• New plain-exponential time classes for graph homomorphism
• Improved upper bounds for vertex cover
• Strong computational lower bounds via parameterized complexity
• On the complexity of H-coloring
• A note on the complexity of the chromatic number problem
• Counting \(H-\)colorings of partial \(k-\)trees
• Which problems have strongly exponential complexity?
• Exact algorithm for graph homomorphism and locally injective graph homomorphism
• Exact algorithms for graph homomorphisms
• Towards Sharp Inapproximability for Any 2-CSP
• The Time Complexity of Constraint Satisfaction
• Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Set Partitioning via Inclusion-Exclusion
• Labelling Graphs with a Condition at Distance 2
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Parameterized Algorithms

This page was built for publication: Lower Bounds for the Graph Homomorphism Problem