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
∙
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
∙
01/24/2023
Treewidth is NP-Complete on Cubic Graphs (and related results)
In this paper, we give a very simple proof that Treewidth is NP-complete...
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
∙
02/01/2021