A. Pieterse

activity

20152025

most citedSparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT

3 citations · 3 across the 6 of their papers we have counts for

collaborators

Showing 2020Show all

2 papers · 1 filter

cs.CC2020

Sparsification Lower Bounds for List $H$ -Coloring

Hubie Chen, Bart M. P. Jansen, Karolina Okrasa +2

We investigate the List $H$ -Coloring problem, the generalization of graph coloring that asks whether an input graph $G$ admits a homomorphism to the undirected graph $H$ (possibly…

cs.DS2020

Approximate Turing Kernelization for Problems Parameterized by Treewidth

Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse

We extend the notion of lossy kernelization, introduced by Lokshtanov et al. [STOC 2017], to approximate Turing kernelization. An $α$ -approximate Turing kernel for a parameterized…

Sparsification Lower Bounds for List H-Coloring

Approximate Turing Kernelization for Problems Parameterized by Treewidth

Sparsification Lower Bounds for List $H$ -Coloring