research
∙
08/17/2023
The Complexity of Fair Division of Indivisible Items with Externalities
We study the computational complexity of fairly allocating a set of indi...
share
research
∙
07/03/2023
Complexity Dichotomies for the Maximum Weighted Digraph Partition Problem
We introduce and study a new optimization problem on digraphs, termed Ma...
research
∙
05/11/2023
Complexity of Efficient Outcomes in Binary-Action Polymatrix Games with Implications for Coordination Problems
We investigate the difficulty of finding economically efficient solution...
research
∙
04/04/2023
Determinantal Sieving
We introduce determinantal sieving, a new, remarkably powerful tool in t...
research
∙
03/21/2023
Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source
We consider the influence maximization problem over a temporal graph, wh...
research
∙
12/01/2022
An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set
We study the CONNECTED η-TREEDEPTH DELETION problem where the input inst...
research
∙
08/18/2022
On the parameterized complexity of symmetric directed multicut
We study the problem Symmetric Directed Multicut from a parameterized co...
research
∙
01/18/2022
The Parameterized Complexity of Welfare Guarantees in Schelling Segregation
Schelling's model considers k types of agents each of whom needs to sele...
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
∙
12/16/2021
Minimizing Reachability Times on Temporal Graphs via Shifting Labels
We study how we can accelerate the spreading of information in temporal ...
research
∙
09/28/2021
A Unifying Framework for Characterizing and Computing Width Measures
Algorithms for computing or approximating optimal decompositions for dec...
research
∙
06/10/2021
Valued Authorization Policy Existence Problem: Theory and Experiments
Recent work has shown that many problems of satisfiability and resilienc...
research
∙
11/30/2020
Integer Programming and Incidence Treedepth
Recently a strong connection has been shown between the tractability of ...
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
∙
07/08/2020
Extending Nearly Complete 1-Planar Drawings in Polynomial Time
The problem of extending partial geometric graph representations such as...
research
∙
06/28/2020
A Polynomial Kernel for Line Graph Deletion
The line graph of a graph G is the graph L(G) whose vertex set is the ed...
research
∙
04/25/2020
Extending Partial 1-Planar Drawings
Algorithmic extension problems of partial graph representations such as ...
research
∙
02/18/2020
Manipulating Districts to Win Elections: Fine-Grained Complexity
Gerrymandering is a practice of manipulating district boundaries and loc...
research
∙
02/04/2020
Removing Connected Obstacles in the Plane is FPT
Given two points in the plane, a set of obstacles defined by closed curv...
research
∙
11/11/2019
A polynomial kernel for 3-leaf power deletion
A graph G is an ℓ-leaf power of a tree T if V(G) is equal to the set of ...
research
∙
11/09/2019
A Polynomial Kernel for Paw-Free Editing
For a fixed graph H, the H-free-editing problem asks whether we can modi...
research
∙
11/04/2019
On Clustering Incomplete Data
We study fundamental clustering problems for incomplete data. In this se...
research
∙
08/27/2019
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
We develop a framework for applying treewidth-based dynamic programming ...
research
∙
10/01/2018
Towards Cereceda's conjecture for planar graphs
The reconfiguration graph R_k(G) of the k-colourings of a graph G has as...
research
∙
02/22/2018
Complexity of the Steiner Network Problem with Respect to the Number of Terminals
In the Directed Steiner Network problem we are given an arc-weighted dig...
research
∙
12/11/2017
How to navigate through obstacles?
Given a set of obstacles and two points, is there a path between the two...
research
∙
11/06/2017