13 citations · 77 across the 56 of their papers we have counts for
11 papers · 1 filter
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…
Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth
Marta Piecyk, Paweł Rzążewski
For graphs , a homomorphism from to is an edge-preserving mapping from to . In the list homomorphism problem, denoted by \textsc{LHom}(), we are given…
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…
Quasi-polynomial-time algorithm for Independent Set in -free graphs via shrinking the space of induced paths
Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski
In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showed a quasi-polynomial-time algorithm for Maximum Weight Independent Set in -free graphs, that is, graphs…
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,…
Parameterized Inapproximability of Independent Set in -Free Graphs
Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai +1
We study the Independent Set (IS) problem in -free graphs, i.e., graphs excluding some fixed graph as an induced subgraph. We prove several inapproximability results both fo…