Siani Smith

activity

20202025

most citedPartitioning H-Free Graphs of Bounded Diameter

3 citations · 8 across the 17 of their papers we have counts for

collaborators

Showing 2022Show all

5 papers · 1 filter

cs.DM2022

Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-graphs

Vadim Lozin, Barnaby Martin, Sukanya Pandey +4

For a fixed set $H$ of graphs, a graph $G$ is $H$ -subgraph-free if $G$ does not contain any $H \in H$ as a (not necessarily induced) subgraph. A recently propo…

math.CO2022★ 1 cited

Complexity Framework For Forbidden Subgraphs I: The Framework

Matthew Johnson, Barnaby Martin, Jelle J. Oostveen +4

For any particular class of graphs, algorithms for computational problems restricted to the class often rely on structural properties that depend on the specific problem at hand. T…

cs.CC2022

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs

Matthew Johnson, Barnaby Martin, Siani Smith +3

We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree $3$ (also known as subcubic graphs). This improves…

math.CO2022

Few Induced Disjoint Paths for $H$ -Free Graphs

Barnaby Martin, Daniël Paulusma, Siani Smith +1

Paths $P^{1}, \dots, P^{k}$ in a graph $G = (V, E)$ are mutually induced if any two distinct $P^{i}$ and $P^{j}$ have neither common vertices nor adjacent vertices. For a fixed integer $k$ , th…

math.CO2022

Induced Disjoint Paths and Connected Subgraphs for $H$ -Free Graphs