Exact algorithm for graph homomorphism and locally injective graph homomorphism

DOI10.1016/J.IPL.2014.02.012MaRDI QIDQ2446599zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Paweł Rzążewski

Publication date 17 April 2014

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

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

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)

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$.

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

Cites work

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

Cited in

(9)

• An efficient algorithm to recognize locally equivalent graphs
• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
• 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
• scientific article; zbMATH DE number 7651213 (Why is no real title available?)
• 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)