Computing list homomorphisms in geometric intersection graphs

DOI10.1007/978-3-031-15914-5_23MaRDI QIDQ6039432zbMATH OpenFDO

Authors Sándor Kisfaludi-Bak, Karolina Okrasa, Paweł Rzążewski

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/2202.08896, https://aaltodoc.aalto.fi/handle/123456789/117888

zbMATH Keywords

graph homomorphismsexponential time hypothesisgeometric intersection graphssubexponential-time algorithms

Mathematics Subject Classification ID

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

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 extsc{LHom}($H$), the instance is a graph $G$, whose every vertex is equipped with a subset of $V(H)$, called list. We ask whether 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 extsc{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 extsc{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 exactly coincides with the analogous dichotomy for graphs excluding a fixed path as an induced subgraph [Okrasa, Rzk{a}.zewski, STACS 2021]. Then we turn our attention to subclasses of string graphs, defined as intersections of fat objects. We observe that the (non)existence of subexponential-time algorithms in such classes is closely related to the size $mathrmmrc(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 $mathrmmrc(H)$ that guarantees the existence of a subexponential-time algorithm for extsc{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. Finally, we discuss possible extensions of our results to weighted generalizations of extsc{LHom}($H$).

Cites work

• scientific article; zbMATH DE number 7053376 (Why is no real title available?)
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• Algorithmic graph theory and perfect graphs
• Algorithms – ESA 2005
• Approximation and Online Algorithms
• EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
• ETH-tight algorithms for long path and cycle on unit disk graphs
• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• Fine-grained complexity of coloring unit disks and balls
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Graph theory for systems biology: interval graphs, motifs, and pattern recognition
• Intersection graphs of segments
• Max-tolerance graphs as intersection graphs
• On the complexity of k-SAT
• On the exact complexity of Hamiltonian Cycle and \(q\)-Colouring in disk graphs
• Optimality program in segment and string graphs
• Representation of a finite graph by a set of intervals on the real line
• Separators for sphere-packings and nearest neighbor graphs
• String graphs. I: The number of critical nonstring graphs is infinite
• String graphs. II: Recognizing string graphs is NP-hard
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• The complexity of colouring problems on dense graphs
• Unit disk graphs
• Which problems have strongly exponential complexity?

Cited in

(2)

• Sparse outerstring graphs have logarithmic treewidth
• A clique-based separator for intersection graphs of geodesic disks in \(\mathbb{R}^2\)

This page was built for publication: Computing list homomorphisms in geometric intersection graphs

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