Subexponential algorithms for variants of homomorphism problem in string graphs

Karolina Okrasa, Paweł Rzążewski

We consider the complexity of finding weighted homomorphisms from intersection graphs of curves (string graphs) with $n$ vertices to a fixed graph $H$. We provide a complete dichot…