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