research
∙
07/11/2023
Computing Subset Vertex Covers in H-Free Graphs
We consider a natural generalization of Vertex Cover: the Subset Vertex ...
share
research
∙
07/03/2023
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Dynamic programming on various graph decompositions is one of the most f...
research
∙
05/02/2023
Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem
We study Steiner Forest on H-subgraph-free graphs, that is, graphs that ...
research
∙
05/01/2023
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
For any finite set ℋ = {H_1,…,H_p} of graphs, a graph is ℋ-subgraph-free...
research
∙
11/25/2022
Complexity Framework for Forbidden Subgraphs: When Hardness Is Not Preserved under Edge Subdivision
A graph G is H-subgraph-free if G does not contain H as a (not necessari...
research
∙
11/23/2022
Complexity Framework For Forbidden Subgraphs
For any finite set ℋ = {H_1,…,H_p} of graphs, a graph is ℋ-subgraph-free...
research
∙
11/22/2022
Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
We show that Edge Multiway Cut (also called Multiterminal Cut) and Node ...
research
∙
07/11/2022
Parameterized Complexity of Streaming Diameter and Connectivity Problems
We initiate the investigation of the parameterized complexity of Diamete...
research
∙
03/07/2022
Few Induced Disjoint Paths for H-Free Graphs
Paths P^1,…,P^k in a graph G=(V,E) are mutually induced if any two disti...
research
∙
02/23/2022
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
Paths P_1,…, P_k in a graph G=(V,E) are mutually induced if any two dist...
research
∙
11/19/2021
Streaming Deletion Problems Parameterized by Vertex Cover
Streaming is a model where an input graph is provided one edge at a time...
research
∙
11/03/2021
The Parameterized Complexity of the Survivable Network Design Problem
For the well-known Survivable Network Design Problem (SNDP) we are given...
research
∙
05/13/2021
Disjoint Paths and Connected Subgraphs for H-Free Graphs
The well-known Disjoint Paths problem is to decide if a graph contains k...
research
∙
12/17/2020
Induced Disjoint Paths in AT-free Graphs
Paths P_1,…,P_k in a graph G=(V,E) are mutually induced if any two disti...
research
∙
04/16/2020
Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
We consider the classical problems (Edge) Steiner Tree and Vertex Steine...
research
∙
03/06/2020
Algorithms for the rainbow vertex coloring problem on graph classes
Given a vertex-colored graph, we say a path is a rainbow vertex path if ...
research
∙
10/02/2019
Subexponential-time algorithms for finding large induced sparse subgraphs
Let C and D be hereditary graph classes. Consider the following problem:...
research
∙
11/16/2018
Nearly ETH-Tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
The Planar Steiner Tree problem is one of the most fundamental NP-comple...
research
∙
10/02/2018
A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs
We show that Odd Cycle Transversal and Vertex Multiway Cut admit determi...
research
∙
08/27/2018
Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
A fundamental graph problem is to recognize whether the vertex set of a ...
research
∙
07/19/2018
Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
We consider two optimization problems in planar graphs. In Maximum Weigh...
research
∙
06/05/2018
Fast Dynamic Programming on Graph Decompositions
In this paper, we consider tree decompositions, branch decompositions, a...
research
∙
04/11/2018
Subexponential-time Algorithms for Maximum Independent Set in P_t-free and Broom-free Graphs
In algorithmic graph theory, a classic open question is to determine the...
research
∙
03/09/2018