research
∙
08/29/2023
FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
We study the α-Fixed Cardinality Graph Partitioning (α-FCGP) problem, th...
share
research
∙
08/01/2023
Structural Parameterizations of the Biclique-Free Vertex Deletion Problem
In this work, we study the Biclique-Free Vertex Deletion problem: Given ...
research
∙
04/04/2023
Determinantal Sieving
We introduce determinantal sieving, a new, remarkably powerful tool in t...
research
∙
02/01/2023
Parameterized Algorithms for Colored Clustering
In the Colored Clustering problem, one is asked to cluster edge-colored ...
research
∙
12/28/2022
Induced Matching below Guarantees: Average Paves the Way for Fixed-Parameter Tractability
In this work, we study the Induced Matching problem: Given an undirected...
research
∙
12/14/2022
Correlating Theory and Practice in Finding Clubs and Plexes
Finding large "cliquish" subgraphs is a classic NP-hard graph problem. I...
research
∙
11/13/2022
Kernelization for Partial Vertex Cover via (Additive) Expansion Lemma
Given a graph and two integers k and ℓ, Partial Vertex Cover asks for a ...
research
∙
06/14/2022
The Complexity of Finding Fair Many-to-One Matchings
We analyze the (parameterized) computational complexity of "fair" varian...
research
∙
05/16/2022
Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences
We study stable matching problems where agents have multilayer preferenc...
research
∙
03/11/2022
Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees
Vertex Cover parameterized by the solution size k is the quintessential ...
research
∙
01/14/2022
Covering Many (or Few) Edges with k Vertices in Sparse Graphs
We study the following two fixed-cardinality optimization problems (a ma...
research
∙
03/05/2021
Essentially Tight Kernels for (Weakly) Closed Graphs
We study kernelization of classic hard graph problems when the input gra...
research
∙
02/23/2021
A Refined Complexity Analysis of Fair Districting over Graphs
We study the NP-hard Fair Connected Districting problem: Partition a ver...
research
∙
02/17/2021
The Complexity of Gerrymandering Over Graphs: Paths and Trees
Roughly speaking, gerrymandering is the systematic manipulation of the b...
research
∙
07/23/2020
Detecting and Enumerating Small Induced Subgraphs in c-Closed Graphs
Fox et al. [SIAM J. Comp. 2020] introduced a new parameter, called c-clo...
research
∙
07/10/2020
Computing Dense and Sparse Subgraphs of Weakly Closed Graphs
A graph G is weakly γ-closed if every induced subgraph of G contains one...
research
∙
05/29/2020
Parameterized Complexity of Min-Power Asymmetric Connectivity
We investigate parameterized algorithms for the NP-hard problem Min-Powe...
research
∙
05/08/2020
Exploiting 𝐜-Closure in Kernelization Algorithms for Graph Problems
A graph is c-closed if every pair of vertices with at least c common nei...
research
∙
02/12/2020
Complexity of Combinatorial Matrix Completion With Diameter Constraints
We thoroughly study a novel and still basic combinatorial matrix complet...
research
∙
02/03/2020
Parameterized Algorithms for Matrix Completion With Radius Constraints
Considering matrices with missing entries, we study NP-hard matrix compl...
research
∙
01/09/2020