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 ...
share
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
∙
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/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
∙
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
∙
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
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