Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

DOI10.1016/J.TCS.2015.01.028MaRDI QIDQ2348037zbMATH OpenOpenAlexFDO

Authors Steven Chaplick, Pim Van 't Hof, Daniël Paulusma, Marek Tesař, Jiří Fiala

Publication date 10 June 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

bounded degreebounded treewidthcomputational complexitylocally constrained graph homomorphisms

Mathematics Subject Classification ID

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

Abstract: A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or injective, respectively. We prove that the problems of testing whether a given graph G allows a homomorphism to a given graph H that is locally bijective, surjective, or injective, respectively, are NP-complete, even when G has pathwidth at most 5, 4, or 2, respectively, or when both G and H have maximum degree 3. We complement these hardness results by showing that the three problems are polynomial-time solvable if G has bounded treewidth and in addition G or H has bounded maximum degree.

Recommendations

• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Exact algorithm for graph homomorphism and locally injective graph homomorphism
• Complexity of locally-injective homomorphisms to tournaments
• Locally constrained graph homomorphisms and equitable partitions

Cites work

• A complete complexity classification of the role assignment problem
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Cantor--Bernstein type theorem for locally constrained graph homomorphisms
• Comparing universal covers in polynomial time
• Complexity of locally injective homomorphism to the Theta graphs
• Computing role assignments of proper interval graphs in polynomial time
• Constructing 5-Arc-Transitive Cubic Graphs
• Covering regular graphs
• Finite common coverings of pairs of regular graphs
• Fixed-parameter complexity of \(\lambda\)-labelings
• Graph Transformations
• Homomorphisms of derivative graphs
• How hard is it to determine if a graph has a 2-role assignment?
• scientific article; zbMATH DE number 1696534 (Why is no real title available?)
• scientific article; zbMATH DE number 4070305 (Why is no real title available?)
• scientific article; zbMATH DE number 91031 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1236360 (Why is no real title available?)
• scientific article; zbMATH DE number 2080268 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 3246034 (Why is no real title available?)
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
• Locally injective homomorphism to the simple weight graphs
• On the complexity of H-coloring
• On the computational complexity of partial covers of theta graphs
• Partial covers of graphs
• Role colouring a graph
• The complexity of \(H\)-colouring of bounded degree graphs
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The core of a graph
• The role assignment model nearly fits most social networks
• Treewidth. Computations and approximations

Cited in

(19)

• Role colouring graphs in hereditary classes
• List covering of regular multigraphs
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• Locally constrained graph homomorphisms and equitable partitions
• Exact algorithm for graph homomorphism and locally injective graph homomorphism
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• Computing role assignments of split graphs
• Locally injective homomorphism to the simple weight graphs
• Complexity of locally-injective homomorphisms to tournaments
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• scientific article; zbMATH DE number 5237265 (Why is no real title available?)
• An algorithmic framework for locally constrained homomorphisms
• List covering of regular multigraphs with semi-edges
• An algorithmic framework for locally constrained homomorphisms
• Tabular intermediate logics comparison
• Computational complexity of covering multigraphs with semi-edges: small cases
• Graph homomorphism, monotone classes and bounded pathwidth
• Computational complexity of covering regular trees
• Parameterizing role coloring on forests

This page was built for publication: Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

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