4 papers · 1 filter
On Sparse Hitting Sets: from Fair Vertex Cover to Highway Dimension
Johannes Blum, Yann Disser, Andreas Emil Feldmann +2
We consider the Sparse Hitting Set (Sparse-HS) problem, where we are given a set system with two families of subsets of .…
Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours
François Dross, Krzysztof Fleszar, Karol Węgrzycki +1
In this paper, we study problems of connecting classes of points via noncrossing structures. Given a set of colored terminal points, we want to find a graph for each color that con…
Dynamic data structures for parameterized string problems
Jędrzej Olkowski, Michał Pilipczuk, Mateusz Rychlicki +2
We revisit classic string problems considered in the area of parameterized complexity, and study them through the lens of dynamic data structures. That is, instead of asking for a…
Recoloring Unit Interval Graphs with Logarithmic Recourse Budget
Bartłomiej Bosek, Anna Zych-Pawlewicz
In this paper we study the problem of coloring a unit interval graph which changes dynamically. In our model the unit intervals are added or removed one at the time, and have to be…