Subexponential algorithms for locally constrained homomorphism problems in string graphs

Speaker(s)

Karolina Okrasa

Affiliation

Politechnika Warszawska

Date

Jan. 24, 2019, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

We consider the complexity of finding weighted homomorphisms from string graphs with n vertices to a fixed graph H. We show that there exists an algorithm solving this problem in subexponential time, if H has no two vertices sharing two common neighbors. Otherwise there is no algorithm working in time 2^o(n), unless the Exponential Time Hypothesis fails.

We also show that another problem, called locally injective homomorphism, where we require the homomorphism to be injective on the neighborhood of each vertex, can be solved in subexponential time in string graphs for each target graph H. Analogously, we define locally surjective homomorphism variant, but here the situation appears to be complicated. We show the dichotomy theorem if H is a conntected, simple graph with at least three vertices and  maximum degree 2. If H is isomorphic to P3 or C4, then the existence of a locally surjective homomorphism from a string graph with n vertices to H can be decided in subexponential time, otherwise, assuming ETH, the problem cannot be solved in time 2^o(n).

As a byproduct, we obtain several results concerning the complexity of variants of homomorphism problem in P_t-free graphs.

This is a joint work with Paweł Rzążewski.

---