An algorithmic framework for locally constrained homomorphisms

Bulteau, L.; Dabrowski, K.K.; Köhler, N.; Ordyniak, S.; Paulusma, D.

Abstract

A homomorphism ϕ from a guest graph G to a host graph H is locally bijective, injective or surjective if for every u∈V(G), the restriction of ϕ 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. 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.

Citation

Bulteau, L., Dabrowski, K., Köhler, N., Ordyniak, S., & Paulusma, D. (2022, December). An algorithmic framework for locally constrained homomorphisms. Presented at WG 2022

• Presentation Conference Type: Conference Paper (published)
• Conference Name: WG 2022
• Acceptance Date: Jul 15, 2022
• Online Publication Date: Oct 1, 2022
• Publication Date: 2022
• Deposit Date: Oct 16, 2022
• Publicly Available Date: Oct 17, 2022
• Print ISSN: 0302-9743
• Volume: 13453
• Pages: 114-128
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743,1611-3349
• Book Title: Graph-Theoretic Concepts in Computer Science. WG 2022.
• ISBN: 978-3-031-15913-8
• DOI: https://doi.org/10.1007/978-3-031-15914-5_9
• Public URL: https://durham-repository.worktribe.com/output/1135540