
Balancing the Spread of Two Opinions in Sparse Social Networks
Inspired by the famous Target Set Selection problem, we propose a new di...
read it

FineGrained View on Bribery for Group Identification
Given a set of agents qualifying or disqualifying each other, group iden...
read it

Finding Small MultiDemand Set Covers with Ubiquitous Elements and Large Sets is FixedParameter Tractable
We study a variant of Set Cover where each element of the universe has s...
read it

Integer Programming and Incidence Treedepth
Recently a strong connection has been shown between the tractability of ...
read it

Recognizing Proper TreeGraphs
We investigate the parameterized complexity of the recognition problem f...
read it

Multidimensional Stable Roommates with Master List
Since the early days of research in algorithms and complexity, the compu...
read it

HighMultiplicity Fair Allocation Using Parametric Integer Linear Programming
Using insights from parametric integer linear programming, we significan...
read it

Scheduling Kernels via Configuration LP
Makespan minimization (on parallel identical or unrelated machines) is a...
read it

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...
read it

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...
read it

LengthBounded Cuts: Proper Interval Graphs and Structural Parameters
In the presented paper we study the LengthBounded Cut problem for speci...
read it

Multitype Integer Monoid Optimization and Applications
Configuration integer programs (IP) have been key in the design of algor...
read it

Adapting Stable Matchings to Evolving Preferences
Adaptivity to changing environments and constraints is key to success in...
read it

Voting and Bribing in SingleExponential Time
We introduce a general problem about bribery in voting systems. In the R...
read it

Tight complexity lower bounds for integer linear programming with few constraints
We consider the ILP Feasibility problem: given an integer linear program...
read it

Parameterized Complexity of Fair Vertex Evaluation Problems
A prototypical graph problem is centered around a graph theoretic proper...
read it

Parameterized complexity of fair deletion problems II
Vertex deletion problems are those where given a graph G and a graph pro...
read it

Evaluating and Tuning nfold Integer Programming
In recent years, algorithmic breakthroughs in stringology, computational...
read it

Complexity of the Steiner Network Problem with Respect to the Number of Terminals
In the Directed Steiner Network problem we are given an arcweighted dig...
read it

A Unifying Framework for Manipulation Problems
Manipulation models for electoral systems are a core research theme in s...
read it

Applying Convex Integer Programming: Sum Multicoloring and Bounded Neighborhood Diversity
In the past 30 years, results regarding special classes of integer linea...
read it

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
We study the Steiner Tree problem, in which a set of terminal vertices n...
read it
Dušan Knop
is this you? claim profile