research
∙
08/10/2023
Comparing Width Parameters on Graph Classes
We study how the relationship between non-equivalent width parameters ch...
share
research
∙
07/11/2023
Computing Subset Vertex Covers in H-Free Graphs
We consider a natural generalization of Vertex Cover: the Subset Vertex ...
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
∙
04/03/2023
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
The (Perfect) Matching Cut problem is to decide if a graph G has a (perf...
research
∙
01/30/2023
Partitioned Matching Games for International Kidney Exchange
We introduce partitioned matching games as a suitable model for internat...
research
∙
12/23/2022
Matching Cuts in Graphs of High Girth and H-Free Graphs
The (Perfect) Matching Cut is to decide if a graph has a (perfect) match...
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/14/2022
Finding Matching Cuts in H-Free Graphs
The NP-complete problem Matching Cut is to decide if a graph has a match...
research
∙
04/14/2022
On The Complexity of Matching Cut for Graphs of Bounded Radius and H-Free Graphs
For a connected graph G=(V,E), a matching M⊆ E is a matching cut of G if...
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
∙
01/27/2022
An Algorithmic Framework for Locally Constrained Homomorphisms
A homomorphism f from a guest graph G to a host graph H is locally bijec...
research
∙
01/02/2022
Classifying Subset Feedback Vertex Set for H-Free Graphs
In the Feedback Vertex Set problem, we aim to find a small set S of vert...
research
∙
11/23/2021
Colouring Generalized Claw-Free Graphs and Graphs of Large Girth: Bounding the Diameter
For a fixed integer, the k-Colouring problem is to decide if the vertice...
research
∙
09/14/2021
Computing Balanced Solutions for Large International Kidney Exchange Schemes
To overcome incompatibility issues, kidney patients may swap their donor...
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
∙
05/10/2021
Partitioning H-Free Graphs of Bounded Diameter
A natural way of increasing our understanding of NP-complete graph probl...
research
∙
05/06/2021
Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
We prove new complexity results for Feedback Vertex Set and Even Cycle T...
research
∙
04/21/2021
Acyclic, Star, and Injective Colouring: Bounding the Diameter
We examine the effect of bounding the diameter for well-studied variants...
research
∙
04/21/2021
QCSP on Reflexive Tournaments
We give a complexity dichotomy for the Quantified Constraint Satisfactio...
research
∙
01/19/2021
Colouring Graphs of Bounded Diameter in the Absence of Small Cycles
For k≥ 1, a k-colouring c of G is a mapping from V(G) to {1,2,…,k} such ...
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
∙
12/17/2020
Hard Problems That Quickly Become Very Easy
A graph class is hereditary if it is closed under vertex deletion. We gi...
research
∙
08/27/2020
The complexity of L(p,q)-Edge-Labelling
We classify the complexity of L(p,q)-Edge-k-Labelling in the sense that ...
research
∙
08/21/2020
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs
A k-colouring c of a graph G is a mapping V(G) to 1,2,... k such that c(...
research
∙
08/20/2020
Solving problems on generalized convex graphs via mim-width
A bipartite graph G=(A,B,E) is H-convex, for some family of graphs H, if...
research
∙
08/03/2020
List k-Colouring P_t-Free Graphs with No Induced 1-Subdivision of K_1,s: a Mim-width Perspective
A colouring of a graph G=(V,E) is a mapping c V→{1,2,…} such that c(u)≠ ...
research
∙
08/02/2020
Tree pivot-minors and linear rank-width
Tree-width and its linear variant path-width play a central role for the...
research
∙
07/28/2020
Computing Weighted Subset Transversals in H-Free Graphs
For the Odd Cycle Transversal problem, the task is to find a small set S...
research
∙
06/05/2020
Clique-Width: Harnessing the Power of Atoms
Many NP-complete graph problems are polynomially solvable on graph class...
research
∙
05/28/2020
Computing Subset Transversals in H-Free Graphs
We study the computational complexity of two well-known graph transversa...
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
∙
04/10/2020
Colouring (sP_1+P_5)-Free Graphs: a Mim-Width Perspective
We prove that the class of (K_t,sP_1+P_5)-free graphs has bounded mim-wi...
research
∙
04/10/2020
Bounding the Mim-Width of Hereditary Graph Classes
A large number of NP-hard graph problems become polynomial-time solvable...
research
∙
10/11/2019
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal
Let vc(G), fvs(G) and oct(G), respectively, denote the size of a minimum...
research
∙
08/01/2019
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
A graph is H-free if it contains no induced subgraph isomorphic to H. We...
research
∙
01/07/2019
On the Parameterized Complexity of k-Edge Colouring
For every fixed integer k ≥ 1, we prove that k-Edge Colouring is fixed-p...
research
∙
01/02/2019
Clique-Width for Hereditary Graph Classes
Clique-width is a well-studied graph parameter owing to its use in under...
research
∙
11/29/2018
Graph Isomorphism for (H_1,H_2)-free Graphs: An Almost Complete Dichotomy
We consider the Graph Isomorphism problem for classes of graphs characte...
research
∙
10/20/2018
Simple Games versus Weighted Voting Games: Bounding the Critical Threshold Value
A simple game (N,v) is given by a set N of n players and a partition of ...
research
∙
10/10/2018
Classifying k-Edge Colouring for H-free Graphs
A graph is H-free if it does not contain an induced subgraph isomorphic ...
research
∙
10/02/2018
Contracting to a Longest Path in H-Free Graphs
We prove two dichotomy results for detecting long paths as patterns in a...
research
∙
08/10/2018
Finding a Small Number of Colourful Components
A partition (V_1,...,V_k) of the vertex set of a graph G with a (not nec...
research
∙
05/21/2018
Colouring Square-Free Graphs without Long Induced Paths
The complexity of Colouring is fully understood for H-free graphs, but ...
research
∙
05/06/2018
Simple Games versus Weighted Voting Games
A simple game (N,v) is given by a set N of n players and a partition of ...
research
∙
04/30/2018
Colouring (P_r+P_s)-Free Graphs
The k-Colouring problem is to decide if the vertices of a graph can be c...
research
∙
03/09/2018
