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