research
∙
07/13/2023
Establishing Herd Immunity is Hard Even in Simple Geometric Networks
We study the following model of disease spread in a social network. At f...
share
research
∙
07/11/2023
Maximizing Social Welfare in Score-Based Social Distance Games
Social distance games have been extensively studied as a coalition forma...
research
∙
02/27/2023
Host Community Respecting Refugee Housing
We propose a novel model for refugee housing respecting the preferences ...
research
∙
01/24/2023
Treewidth is NP-Complete on Cubic Graphs (and related results)
In this paper, we give a very simple proof that Treewidth is NP-complete...
research
∙
07/03/2022
On Polynomial Kernels for Traveling Salesperson Problem and its Generalizations
For many problems, the important instances from practice possess certain...
research
∙
02/24/2022
Polynomial Kernels for Tracking Shortest Paths
Given an undirected graph G=(V,E), vertices s,t∈ V, and an integer k, Tr...
research
∙
02/18/2022
Hedonic Diversity Games: A Complexity Picture with More than Two Colors
Hedonic diversity games are a variant of the classical Hedonic games des...
research
∙
02/03/2022
Multivariate Algorithmics for Eliminating Envy by Donating Goods
Fairly dividing a set of indivisible resources to a set of agents is of ...
research
∙
08/03/2021
Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set
Consider a vertex-weighted graph G with a source s and a target t. Track...
research
∙
05/21/2021
Balancing the Spread of Two Opinions in Sparse Social Networks
Inspired by the famous Target Set Selection problem, we propose a new di...
research
∙
05/18/2021
Fine-Grained View on Bribery for Group Identification
Given a set of agents qualifying or disqualifying each other, group iden...
research
∙
04/20/2021
Finding Small Multi-Demand Set Covers with Ubiquitous Elements and Large Sets is Fixed-Parameter Tractable
We study a variant of Set Cover where each element of the universe has s...
research
∙
11/30/2020
Integer Programming and Incidence Treedepth
Recently a strong connection has been shown between the tractability of ...
research
∙
11/23/2020
Recognizing Proper Tree-Graphs
We investigate the parameterized complexity of the recognition problem f...
research
∙
09/29/2020
Multidimensional Stable Roommates with Master List
Since the early days of research in algorithms and complexity, the compu...
research
∙
05/11/2020
High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming
Using insights from parametric integer linear programming, we significan...
research
∙
03/04/2020
Scheduling Kernels via Configuration LP
Makespan minimization (on parallel identical or unrelated machines) is a...
research
∙
02/10/2020
Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
In the Steiner Tree problem we are given an edge weighted undirected gra...
research
∙
11/21/2019
Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
We continue and extend previous work on the parameterized complexity ana...
research
∙
10/08/2019
Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters
In the presented paper we study the Length-Bounded Cut problem for speci...
research
∙
09/16/2019
Multitype Integer Monoid Optimization and Applications
Configuration integer programs (IP) have been key in the design of algor...
research
∙
07/02/2019
Adapting Stable Matchings to Evolving Preferences
Adaptivity to changing environments and constraints is key to success in...
research
∙
12/05/2018
Voting and Bribing in Single-Exponential Time
We introduce a general problem about bribery in voting systems. In the R...
research
∙
11/03/2018
Tight complexity lower bounds for integer linear programming with few constraints
We consider the ILP Feasibility problem: given an integer linear program...
research
∙
03/19/2018
Parameterized Complexity of Fair Vertex Evaluation Problems
A prototypical graph problem is centered around a graph theoretic proper...
research
∙
03/19/2018
Parameterized complexity of fair deletion problems II
Vertex deletion problems are those where given a graph G and a graph pro...
research
∙
02/25/2018
Evaluating and Tuning n-fold Integer Programming
In recent years, algorithmic breakthroughs in stringology, computational...
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
∙
01/29/2018
A Unifying Framework for Manipulation Problems
Manipulation models for electoral systems are a core research theme in s...
research
∙
11/06/2017
Applying Convex Integer Programming: Sum Multicoloring and Bounded Neighborhood Diversity
In the past 30 years, results regarding special classes of integer linea...
research
∙
10/02/2017