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
∙
11/07/2022
Complexity Classification Transfer for CSPs via Algebraic Products
We study the complexity of infinite-domain constraint satisfaction probl...
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
∙
06/24/2021
The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation
Let A be an idempotent algebra on a finite domain. By mediating between ...
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
∙
04/01/2021
The complete classification for quantified equality constraints
We prove that QCSP(ℕ;x=y→ y=z) is PSpace-complete, settling a question o...
research
∙
02/15/2021
Depth lower bounds in Stabbing Planes for combinatorial principles
We prove logarithmic depth lower bounds in Stabbing Planes for the class...
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
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/04/2020
Proof complexity and the binary encoding of combinatorial principles
We consider Proof Complexity in light of the unusual binary encoding of ...
research
∙
11/01/2019
Sherali-Adams and the binary encoding of combinatorial principles
We consider the Sherali-Adams (SA) refutation system together with the u...
research
∙
06/29/2019
QCSP monsters and the demise of the Chen Conjecture
We give a surprising classification for the computational complexity of ...
research
∙
09/08/2018
Resolution and the binary encoding of combinatorial principles
We investigate the size complexity of proofs in Res(s) -- an extension o...
research
∙
07/03/2018
The complexity of disjunctive linear Diophantine constraints
We study the Constraint Satisfaction Problem CSP(A), where A is first-or...
research
∙
05/05/2018
Classification transfer for qualitative reasoning problems
We study formalisms for temporal and spatial reasoning in the modern con...
research
∙
03/09/2018
Disconnected Cuts in Claw-free Graphs
A disconnected cut of a connected graph is a vertex cut that itself also...
research
∙
09/27/2017
Surjective H-Colouring over Reflexive Digraphs
The Surjective H-Colouring problem is to test if a given graph allows a ...
research
∙
04/26/2012
Containment, Equivalence and Coreness from CSP to QCSP and beyond
The constraint satisfaction problem (CSP) and its quantified extensions,...
research
∙
09/28/2009