## Computing List Homomorphisms in Geometric Intersection Graphs

Loading...

##### Journal Title

##### Journal ISSN

##### Volume Title

A4 Artikkeli konferenssijulkaisussa

This publication is imported from Aalto University research portal.

View publication in the Research portal

View/Open full text file from the Research portal

Other link related to publication

View publication in the Research portal

View/Open full text file from the Research portal

Other link related to publication

##### Date

2022

##### Department

Department of Computer Science

Warsaw University of Technology

Warsaw University of Technology

##### Major/Subject

##### Mcode

##### Degree programme

##### Language

en

##### Pages

15

313-327

313-327

##### Series

Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Revised Selected Papers, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Volume 13453 LNCS

##### Abstract

A homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H). Let H be a fixed graph with possible loops. In the list homomorphism problem, denoted by LHom(H), the instance is a graph G, whose every vertex is equipped with a subset of V(H), called list. We ask if there exists a homomorphism from G to H, such that every vertex from G is mapped to a vertex from its list. We study the complexity of the LHom(H) problem in intersection graphs of various geometric objects. In particular, we are interested in answering the question for what graphs H and for what types of geometric objects, the LHom(H) problem can be solved in time subexponential in the number of vertices of the instance. We fully resolve this question for string graphs, i.e., intersection graphs of continuous curves in the plane. Quite surprisingly, it turns out that the dichotomy coincides with the analogous dichotomy for graphs excluding a fixed path as an induced subgraph [Okrasa, Rzążewski, STACS 2021]. Then we turnour attention to intersections of fat objects. We observe that the (non) existence of subexponential-time algorithms in such classes is closely related to the size $$\textrm{mrc}(H)$$ of a maximum reflexive clique in H, i.e., maximum number of pairwise adjacent vertices, each of which has a loop. We study the maximum value of $$\textrm{mrc}(H)$$ that guarantees the existence of a subexponential-time algorithm for LHom(H) in intersection graphs of (i) convex fat objects, (ii) fat similarly-sized objects, and (iii) disks. In the first two cases we obtain optimal results, by giving matching algorithms and lower bounds.##### Description

Funding Information: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement no. 714704. Pawel Rzażewski – Supported by Polish National Science Centre grant no. 2018/31/D/ ST6/00062.

##### Keywords

Exponential Time Hypothesis, Geometric intersection graphs, Graph homomorphisms, Subexponential-time algorithms

##### Citation

Kisfaludi-Bak , S , Okrasa , K & Rzążewski , P 2022 , Computing List Homomorphisms in Geometric Intersection Graphs . in M A Bekos & M Kaufmann (eds) , Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Revised Selected Papers . Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) , vol. 13453 LNCS , Springer , pp. 313-327 , International Workshop on Graph-Theoretic Concepts in Computer Science , Tübingen , Germany , 22/06/2022 . https://doi.org/10.1007/978-3-031-15914-5_23