Subexponential algorithms for variants of the homomorphism problem in string graphs.

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 (n 2 / 3 log ⁡ 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 (n log ⁡ n) in string graphs. For locally surjective homomorphisms we show a dichotomy for H being a path or a cycle. If H is P 3 or C 4 , then the problem can be solved in time 2 O (n 2 / 3 log 3 / 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. [ABSTRACT FROM AUTHOR]