17 papers · 1 filter
Tight Competitive Bounds for Online Matching on Forests
Bartłomiej Bosek, Grzegorz Gutowski, Paweł Putra +1
We study the online matching problem, its fractional relaxation, and the fractional online vertex cover problem on forests whose edges arrive one at a time in an arbitrary order. M…
Partially Dynamic Algorithms for Single-Source Temporal Paths
Davide Bilò, Bartłomiej Bosek, Jadwiga Czyżewska +3
We present efficient partially dynamic algorithms for maintaining earliest arrival times from a fixed source in temporal digraphs with vertices. For the incremental scenario wh…
Almost Linear 3-Spanners of Temporal Cliques
Julia Baligacs, Davide Bilò, Václav Blažej +2
Temporal graphs model dynamic networks by assigning positive integer time labels to the edges, while information propagates along temporal paths, whose edge labels are traversed in…
Online and Incremental Fractional Vertex Cover on Trees
Júlia Baligács, Bartłomiej Bosek, Yann Disser +5
In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori…
A tight lower bound for malicious online bipartite matching with limited recourse budget
Julia Baligacs, Bartłomiej Bosek, Paweł Putra +2
We study one-sided online bipartite matching with recourse. In this setting, one side of a bipartite graph is known in advance, while vertices on the other side arrive online toget…
Dynamic domination and independence in sparse graphs
Bartłomiej Bosek, Wojciech Nadara, Michał Pilipczuk +1
Let be a class of graphs of bounded expansion and be fixed. We give a dynamic data structure that for a given dynamic graph , updated by edge i…
Dynamic data structures for twin-ordered matrices
Bartłomiej Bosek, Jadwiga Czyżewska, Evangelos Kipouridis +4
We present a dynamic data structure for representing binary matrices that are -twin-ordered, for a~fixed parameter . Our structure supports cell queries and singl…
Fair Vertex Problems Parameterized by Cluster Vertex Deletion
Tomáš Masařík, Jędrzej Olkowski, Anna Zych-Pawlewicz
In this paper we study fair variants of MSO definable problems parameterized by cluster vertex deletion number, i.e., the smallest number of vertices required to be removed fro…
Dynamic Parameterized Feedback Problems in Tournaments
Anna Zych-Pawlewicz, Marek Żochowski
In this paper we present the first dynamic algorithms for the problem of Feedback Arc Set in Tournaments (FAST) and the problem of Feedback Vertex Set in Tournaments (FVST). Our al…
A -Approximation for Tricolored Non-crossing Euclidean TSP
Júlia Baligács, Yann Disser, Andreas Emil Feldmann +1
In the Tricolored Euclidean Traveling Salesperson problem, we are given~ sets of points in the plane and are looking for disjoint tours, each covering one of the sets. Arora (…
Parameterized dynamic data structure for Split Completion
Konrad Majewski, Michał Pilipczuk, Anna Zych-Pawlewicz
We design a randomized data structure that, for a fully dynamic graph updated by edge insertions and deletions and integers fixed upon initialization, maintains the answ…
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…
Compact representation for matrices of bounded twin-width
Michał Pilipczuk, Marek Sokołowski, Anna Zych-Pawlewicz
For every fixed , we design a data structure that represents a binary matrix that is -twin-ordered. The data structure occupies bits, whi…
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
Jiehua Chen, Wojciech Czerwiński, Yann Disser +8
We present a data structure that in a dynamic graph of treedepth at most , which is modified over time by edge insertions and deletions, maintains an optimum-height elimination…
An exponential lower bound for cut sparsifiers in planar graphs
Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz
Given an edge-weighted graph with a set of terminals, a mimicking network is a graph with the same set of terminals that exactly preserves the sizes of minimum cuts bet…