2 citations · 3 across the 11 of their papers we have counts for
6 papers · 1 filter
The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
Robert Ganian, Thekla Hamm, Viktoriia Korchemna +2
The generic homomorphism problem, which asks whether an input graph admits a homomorphism into a fixed target graph , has been widely studied in the literature. In this arti…
Complexity of the list homomorphism problem in hereditary graph classes
Karolina Okrasa, Paweł Rzążewski
A homomorphism from a graph to a graph is an edge-preserving mapping from to . For a fixed graph , in the list homomorphism problem, denoted by LHom(), w…
Sparsification Lower Bounds for List -Coloring
Hubie Chen, Bart M. P. Jansen, Karolina Okrasa +2
We investigate the List -Coloring problem, the generalization of graph coloring that asks whether an input graph admits a homomorphism to the undirected graph (possibly…
Full complexity classification of the list homomorphism problem for bounded-treewidth graphs
Karolina Okrasa, Marta Piecyk, Paweł Rzążewski
A homomorphism from a graph to a graph is an edge-preserving mapping from to . Let be a fixed graph with possible loops. In the list homomorphism problem,…
Subexponential-time algorithms for finding large induced sparse subgraphs
Jana Novotná, Karolina Okrasa, Michał Pilipczuk +3
Let and be hereditary graph classes. Consider the following problem: given a graph , find a largest, in terms of the number of vertices…
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 vertices to a fixed graph . We provide a complete dichot…