14 citations · 22 across the 11 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.CC2020
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…
cs.DS2020
Preprocessing Vertex-Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies
Bart M. P. Jansen, Jari J. H. de Kroon
We consider the -free Deletion problem parameterized by the size of a vertex cover, for a range of graph properties . Given an input graph , this problem asks whether ther…
cs.CC2020
Optimal polynomial-time compression for Boolean Max CSP
Bart M. P. Jansen, Michał Włodarczyk
In the Boolean maximum constraint satisfaction problem - Max CSP - one is given a collection of weighted applications of constraints from a finite constraint language , ove…