An algorithmic framework for locally constrained homomorphisms

DOI10.1007/978-3-031-15914-5_9MaRDI QIDQ6039418zbMATH OpenOpenAlexFDO

Authors Laurent Bulteau, Konrad Dabrowski, Noleen Köhler, Sebastian Ordyniak, Daniël Paulusma

Publication date 5 May 2023

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2201.11731, https://eprints.whiterose.ac.uk/187108/1/main.pdf

zbMATH Keywords

(locally constrained) graph homomorphismfracture numberparameterized complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Abstract: A homomorphism $f$ from a guest graph $G$ to a host graph $H$ is locally bijective, injective or surjective if for every $uinV(G)$, the restriction of $f$ to the neighbourhood of $u$ is bijective, injective or surjective, respectively. The corresponding decision problems, LBHOM, LIHOM and LSHOM, are well studied both on general graphs and on special graph classes. Apart from complexity results when the problems are parameterized by the treewidth and maximum degree of the guest graph, the three problems still lack a thorough study of their parameterized complexity. This paper fills this gap: we prove a number of new FPT, W[1]-hard and para-NP-complete results by considering a hierarchy of parameters of the guest graph $G$. For our FPT results, we do this through the development of a new algorithmic framework that involves a general ILP model. To illustrate the applicability of the new framework, we also use it to prove FPT results for the Role Assignment problem, which originates from social network theory and is closely related to locally surjective homomorphisms.

Cites work

• A complete complexity classification of the role assignment problem
• Algebraic Graph Theory
• An application of simultaneous diophantine approximation in combinatorial optimization
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Backdoors to planning
• Comparing universal covers in polynomial time
• Complexity of locally injective homomorphism to the Theta graphs
• Computational complexity of covering disconnected multigraphs
• Computational complexity of covering three-vertex multigraphs
• Computing role assignments of chordal graphs
• Computing role assignments of proper interval graphs in polynomial time
• Computing role assignments of split graphs
• Conjunctive query containment revisited
• Constructing 5-Arc-Transitive Cubic Graphs
• Covering regular graphs
• Dichotomy of the H-quasi-cover problem
• Finite common coverings of pairs of regular graphs
• Fixed-parameter complexity of \(\lambda\)-labelings
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Graph labelings derived from models in distributed computing: A complete complexity classification
• Graph Layout Problems Parameterized by Vertex Cover
• Homomorphisms of derivative graphs
• How hard is it to determine if a graph has a 2-role assignment?
• scientific article; zbMATH DE number 91031 (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 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 3246034 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• Local computations in graphs: the case of cellular edge local computations
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• Locally injective homomorphism to the simple weight graphs
• Minkowski's Convex Body Theorem and Integer Programming
• On the complexity of H-coloring
• On the complexity of role colouring planar graphs, trees and cographs
• On the computational complexity of partial covers of theta graphs
• Packing bipartite graphs with covers of complete bipartite graphs
• Parameterizing role coloring on forests
• Partial covers of graphs
• Regular codes in regular graphs are difficult
• Role colouring a graph
• Role colouring graphs in hereditary classes
• SOFSEM 2005: Theory and Practice of Computer Science
• Sparsity. Graphs, structures, and algorithms
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The role assignment model nearly fits most social networks

Cited in

(5)

• Extended MSO model checking via small vertex integrity
• An algorithmic framework for locally constrained homomorphisms
• Complexity framework for forbidden subgraphs. IV: The Steiner forest problem
• Complexity framework for forbidden subgraphs. IV: The Steiner forest problem
• Graph homomorphism, monotone classes and bounded pathwidth

This page was built for publication: An algorithmic framework for locally constrained homomorphisms

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