research
∙
09/08/2023
Shortest Path with Positive Disjunctive Constraints – a Parameterized Perspective
We study the SHORTEST PATH problem with positive disjunctive constraints...
share
research
∙
08/03/2023
Meta-theorems for Parameterized Streaming Algorithms
The streaming model was introduced to parameterized complexity independe...
research
∙
04/26/2023
Hitting Subgraphs in Sparse Graphs and Geometric Intersection Graphs
We investigate a fundamental vertex-deletion problem called (Induced) Su...
research
∙
11/04/2022
A Framework for Approximation Schemes on Disk Graphs
We initiate a systematic study of approximation schemes for fundamental ...
research
∙
07/25/2022
Boolean and 𝔽_p-Matrix Factorization: From Theory to Practice
Boolean Matrix Factorization (BMF) aims to find an approximation of a gi...
research
∙
01/11/2022
Partial Vertex Cover on Graphs of Bounded Degeneracy
In the Partial Vertex Cover (PVC) problem, we are given an n-vertex grap...
research
∙
04/20/2021
Elimination Distance to Topological-minor-free Graphs is FPT
In the literature on parameterized graph problems, there has been an inc...
research
∙
02/19/2021
Gerrymandering on graphs: Computational complexity and parameterized algorithms
Partitioning a region into districts to favor a particular candidate or ...
research
∙
01/12/2021
Diverse Collections in Matroids and Graphs
We investigate the parameterized complexity of finding diverse sets of s...
research
∙
10/19/2020
EPTAS for k-means Clustering of Affine Subspaces
We consider a generalization of the fundamental k-means clustering for d...
research
∙
09/26/2020
Improved FPT Algorithms for Deletion to Forest-like Structures
The Feedback Vertex Set problem is undoubtedly one of the most well-stud...
research
∙
03/02/2020
ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
We present an algorithm for the extensively studied Long Path and Long C...
research
∙
02/23/2020
Structural Parameterizations with Modulator Oblivion
It is known that problems like Vertex Cover, Feedback Vertex Set and Odd...
research
∙
02/18/2020
Manipulating Districts to Win Elections: Fine-Grained Complexity
Gerrymandering is a practice of manipulating district boundaries and loc...
research
∙
10/01/2019
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
In a reconfiguration version of an optimization problem Q the input is a...
research
∙
05/10/2019
Refined Complexity of PCA with Outliers
Principal component analysis (PCA) is one of the most fundamental proced...
research
∙
04/12/2019
Low-rank binary matrix approximation in column-sum norm
We consider ℓ_1-Rank-r Approximation over GF(2), where for a binary m× n...
research
∙
04/05/2019
Reducing Topological Minor Containment to the Unique Linkage Theorem
In the Topological Minor Containment problem (TMC) problem two undirecte...
research
∙
03/04/2019
Decomposition of Map Graphs with Applications
Bidimensionality is the most common technique to design subexponential-t...
research
∙
02/07/2019
Going Far From Degeneracy
An undirected graph G is d-degenerate if every subgraph of G has a verte...
research
∙
09/22/2018
A 2-Approximation Algorithm for Feedback Vertex Set in Tournaments
A tournament is a directed graph T such that every pair of vertices is ...
research
∙
07/18/2018
Approximation Schemes for Low-Rank Binary Matrix Approximation Problems
We provide a randomized linear time approximation scheme for a generic p...
research
∙
03/16/2018
Parameterized Low-Rank Binary Matrix Approximation
We provide a number of algorithmic results for the following family of p...
research
∙
02/22/2018
