Exact algorithm for graph homomorphism and locally injective graph homomorphism

DOI10.1016/J.IPL.2014.02.012zbMATH Open1285.05130DBLPjournals/ipl/Rzazewski14arXiv1310.3341OpenAlexW1494193561WikidataQ62595912 ScholiaQ62595912MaRDI QIDQ2446599FDOQ2446599

Authors: Paweł Rzążewski 

Publication date: 17 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: For graphs $G$ and $H$, a homomorphism from $G$ to $H$ is a function $varphicolonV(G)oV(H)$, which maps vertices adjacent in $G$ to adjacent vertices of $H$. A homomorphism is locally injective if no two vertices with a common neighbor are mapped to a single vertex in $H$. Many cases of graph homomorphism and locally injective graph homomorphism are NP-complete, so there is little hope to design polynomial-time algorithms for them. In this paper we present an algorithm for graph homomorphism and locally injective homomorphism working in time $mathcal{O}^{\ast }((b+2{)}^{|V(G)|})$, where $b$ is the bandwidth of the complement of $H$.

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

Recommendations

• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• The complexity of locally injective homomorphisms
• Lower bounds for the graph homomorphism problem

zbMATH Keywords

exact algorithmgraph algorithmsgraph homomorphismlocally injective homomorphism\(H(2, 1)\)-labeling

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Graph theory
• Title not available (Why is that?)
• On the complexity of H-coloring
• Labelling Graphs with a Condition at Distance 2
• Exact algorithms for graph homomorphisms
• Title not available (Why is that?)
• A complete complexity classification of the role assignment problem
• Set partitioning via inclusion-exclusion
• Fast exact algorithm for \(L(2,1)\)-labeling of graphs
• Circular chromatic number: A survey
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• Circular Distance Two Labeling and the $\lambda$-Number for Outerplanar Graphs
• On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs
• Title not available (Why is that?)
• Covering regular graphs
• On the computational complexity of partial covers of theta graphs
• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy

Cited In (9)

• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
• An efficient algorithm to recognize locally equivalent graphs
• Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Lower bounds for the graph homomorphism problem
• Title not available (Why is that?)
• An algorithmic framework for locally constrained homomorphisms
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

This page was built for publication: Exact algorithm for graph homomorphism and locally injective graph homomorphism

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