Subexponential algorithms for locally constrained homomorphism problems in string graphs

Prelegent(ci)

Karolina Okrasa

Afiliacja

Politechnika Warszawska

Termin

24 stycznia 2019 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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.

---