Subexponential algorithms for variants of the homomorphism problem in string graphs

Karolina Okrasa , Paweł Rzążewski

Abstract

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 2O(n2/3log⁡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 2O(nlog⁡n) in string graphs. For locally surjective homomorphisms we show a dichotomy for H being a path or a cycle. If H is P3 or C4, then the problem can be solved in time 2O(n2/3log3/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 Pt-free graphs.

Author Karolina Okrasa (FMIS)
Karolina Okrasa,,
- Faculty of Mathematics and Information Science
, Paweł Rzążewski (FMIS / DIPS)
Paweł Rzążewski,,
- Department of Information Processing Systems
Journal seriesJournal of Computer and System Sciences, ISSN 0022-0000, e-ISSN 1090-2724
Issue year2020
Vol109
Pages126-144
Publication size in sheets0.9
Keywords in Polishgrafy przecięć odcinków, grafy przecięć krzywych, złożoność
Keywords in EnglishString graphs, Segment graphs, Subexponential algorithms ETH
ASJC Classification1703 Computational Theory and Mathematics; 1705 Computer Networks and Communications; 2604 Applied Mathematics; 2614 Theoretical Computer Science
Abstract in PolishW pracy pokazujemy dychotomię dla problemu ważonego homomorfizmów w graf H z grafów przecięć odcinków. Charakteryzujemy grafy H, dla których problem da się rozwiązać w czasie podwykładniczym.
DOIDOI:10.1016/j.jcss.2019.12.004
URL https://www.sciencedirect.com/science/article/pii/S0022000019300856
Languageen angielski
Score (nominal)100
Score sourcejournalList
ScoreMinisterial score = 100.0, 12-08-2020, ArticleFromJournal
Publication indicators Scopus Citations = 1; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.334; WoS Impact Factor: 2018 = 1.129 (2) - 2018=1.739 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?