English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We consider the complexity of finding weighted homomorphisms fromintersection graphs of curves (string graphs) with $n$ vertices to a fixedgraph $H$. We provide a complete dichotomy for the problem: if $H$ has no twovertices sharing two common neighbors, then the problem can be solved in time$2^{O(n^{2/3} \log n)}$, otherwise there is no algorithm working in time$2^{o(n)}$, even in intersection graphs of segments, unless the ETH fails. Thisgeneralizes several known results concerning the complexity of computatationalproblems in geometric intersection graphs. Then we consider two variants ofgraph homomorphism problem, called locally injective homomorphism and locallybijective homomorphism, where we require the homomorphism to be injective orbijective on the neighborhood of each vertex. We show that for each targetgraph $H$, both problems can always be solved in time $2^{O(\sqrt{n} \log n)}$in string graphs. For the locally surjecive homomorphism, defined in ananalogous way, the situation seems more complicated. We show the dichotomytheorem for simple connected graphs $H$ with maximum degree 2. If $H$ isisomorphic to $P_3$ or $C_4$, then the existence of a locally surjectivehomomorphism from a string graph with $n$ vertices to $H$ can be decided intime $2^{O(n^{2/3} \log^{3/2} n)}$, otherwise the problem cannot be solved intime $2^{o(n)}$, unless the ETH fails. As a byproduct, we obtain severalresults concerning the complexity of variants of homomorphism problem in$P_t$-free graphs. In particular, we obtain the dichotomy theorem for weightedhomomorphism, analogous to the one for string graphs.

Subexponential algorithms for variants of homomorphism problem in string graphs