research
∙
06/06/2023
Representative set statements for delta-matroids and the Mader delta-matroid
We present representative sets-style statements for linear delta-matroid...
share
research
∙
05/18/2023
Parameterized Complexity of Equality MinCSP
We study the parameterized complexity of MinCSP for so-called equality l...
research
∙
04/04/2023
Determinantal Sieving
We introduce determinantal sieving, a new, remarkably powerful tool in t...
research
∙
08/31/2022
On weighted graph separation problems and flow-augmentation
One of the first application of the recently introduced technique of flo...
research
∙
08/18/2022
On the parameterized complexity of symmetric directed multicut
We study the problem Symmetric Directed Multicut from a parameterized co...
research
∙
08/04/2022
Almost Consistent Systems of Linear Equations
Checking whether a system of linear equations is consistent is a basic c...
research
∙
07/15/2022
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
We study the parameterized problem of satisfying “almost all” constraint...
research
∙
12/31/2021
Preference Swaps for the Stable Matching Problem
An instance I of the Stable Matching Problem (SMP) is given by a biparti...
research
∙
11/05/2021
Directed flow-augmentation
We show a flow-augmentation algorithm in directed graphs: There exists a...
research
∙
09/17/2020
p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms
We introduce and study two natural generalizations of the Connected Vert...
research
∙
07/17/2020
Solving hard cut problems via flow-augmentation
We present a new technique for designing FPT algorithms for graph cut pr...
research
∙
05/05/2020
Many visits TSP revisited
We study the Many Visits TSP problem, where given a number k(v) for each...
research
∙
02/20/2020
On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
We show the existence of an exact mimicking network of k^O(log k) edges ...
research
∙
07/28/2019
Parameterized Pre-coloring Extension and List Coloring Problems
Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the p...
research
∙
10/16/2018
Multi-budgeted directed cuts
We study multi-budgeted variants of the classic minimum cut problem and ...
research
∙
06/24/2018
On r-Simple k-Path and Related Problems Parameterized by k/r
Abasi et al. (2014) and Gabizon et al. (2015) studied the following prob...
research
∙
04/27/2018
Alternative parameterizations of Metric Dimension
A set of vertices W in a graph G is called resolving if for any two dist...
research
∙
02/16/2018
Parameterized Algorithms for Zero Extension and Metric Labelling Problems
We consider the problems ZERO EXTENSION and METRIC LABELLING under the p...
research
∙
01/29/2018