Marta Piecyk

activity

20202026

collaborators

Showing cs.CCShow all

2 papers · 1 filter

cs.CC2020

Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth

Marta Piecyk, Paweł Rzążewski

For graphs $G, H$ , a homomorphism from $G$ to $H$ is an edge-preserving mapping from $V (G)$ to $V (H)$ . In the list homomorphism problem, denoted by \textsc{LHom}( $H$ ), we are given…

cs.CC2020

Full complexity classification of the list homomorphism problem for bounded-treewidth graphs

Karolina Okrasa, Marta Piecyk, Paweł Rzążewski

A homomorphism from a graph $G$ to a graph $H$ is an edge-preserving mapping from $V (G)$ to $V (H)$ . Let $H$ be a fixed graph with possible loops. In the list homomorphism problem,…