Subexponential algorithms for variants of the homomorphism problem in string graphs

Authors:

• Karolina Okrasa,
• Paweł Rzążewski

Abstract

We consider subexponential algorithms finding weighted homomorphisms from intersection graphs of curves (string graphs) with n vertices to a fixed graph H. We provide a complete dichotomy: if H has no two vertices sharing two common neighbors, then the problem can be solved in time 2^{O(n2/3log⁡n)}, otherwise there is no subexponential algorithm, assuming the ETH. Then we consider locally constrained homomorphisms. We show that for each target graph H, the locally injective and locally bijective homomorphism problems can be solved in time 2^O(nlog⁡n) in string graphs. For locally surjective homomorphisms we show a dichotomy for H being a path or a cycle. If H is P₃ or C₄, then the problem can be solved in time 2^{O(n2/3log3/2⁡n)} in string graphs; otherwise, assuming the ETH, there is no subexponential algorithm. As corollaries, we obtain new results concerning the complexity of homomorphism problems in P_t-free graphs.