-
Article
Open AccessHigh-multiplicity N-fold IP via configuration LP
N-fold integer programs (IPs) form an important class of block-structured IPs for which increasingly fast algorithms have recently been developed and successfully applied. We study high-multiplicity N-fold IPs, w...
-
Article
Open AccessFine-grained view on bribery for group identification
Given a set of agents qualifying or disqualifying each other, group identification is the task of identifying a socially qualified subgroup of agents. Social qualification depends on the specific rule used to agg...
-
Chapter and Conference Paper
Establishing Herd Immunity is Hard Even in Simple Geometric Networks
We study the following model of disease spread in a social network. In the beginning, all individuals are either infected or healthy. Next, in discrete rounds, the disease spreads in the network from infected to ...
-
Chapter and Conference Paper
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. Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from s to t is unique...
-
Article
Combinatorial n-fold integer programming and applications
Many fundamental \(\mathsf {NP}\) NP -hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is exponential only in the dimension of the progr...
-
Article
The Clever Shopper Problem
We investigate a variant of the so-called Internet Shop** problem introduced by Blazewicz et al. (Appl. Math. Comput. Sci. 20, 385–390, 2010), where a customer wants to buy a list of products at the lowest poss...
-
Chapter and Conference Paper
Multidimensional Stable Roommates with Master List
Since the early days of research in algorithms and complexity, the computation of stable matchings is a core topic. While in the classic setting the goal is to match up two agents (either from different “gende...
-
Chapter and Conference Paper
Graph Isomorphism Restricted by Lists
The complexity of graph isomorphism (GraphIso) is a famous problem in computer science. For graphs G and H, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restri...
-
Chapter and Conference Paper
Integer Programming and Incidence Treedepth
Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matrix on the other side. To that ...
-
Chapter and Conference Paper
Kernelization of Graph Hamiltonicity: Proper H-Graphs
We obtain new polynomial kernels and compression algorithms for Pat...
-
Article
Parameterized Complexity of Length-bounded Cuts and Multicuts
We study the Minimum Length-Bounded Cut problem where the task is to find a set of edges of a graph such that after removal of this set, the shortest path between two prescribed vertices is at least ...
-
Article
Scheduling meets n-fold integer programming
Scheduling problems are fundamental in combinatorial optimization. Much work has been done on approximation algorithms for NP-hard cases, but relatively little is known about exact solutions when some part of the...
-
Chapter and Conference Paper
Partitioning Graphs into Induced Subgraphs
We study the Partition into \(H\) problem from the parametrized complexity point of view. In the Partition ...
-
Chapter and Conference Paper
Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
This paper settles the computational complexity of model checking of several extensions of the monadic second order (MSO) logic on two classes of graphs: graphs of bounded treewidth and graphs of bounded neighbor...
-
Chapter and Conference Paper
Computational Complexity of Distance Edge Labeling
The problem of Distance Edge Labeling is a variant of Distance Vertex Labeling (also known as \(\mathrm{L}_{2,1}\) la...
-
Chapter and Conference Paper
Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
We study computational complexity of the class of distance-constrained graph labeling problems from the fixed parameter tractability point of view. The parameters studied are neighborhood diversity and clique ...
-
Chapter and Conference Paper
Parametrized Complexity of Length-Bounded Cuts and Multi-cuts
We show that the minimal length-bounded \(L\) -cut can be computed in linear time with respect to
