English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the classical problems (Edge) Steiner Tree and Vertex SteinerTree after restricting the input to some class of graphs characterized by asmall set of forbidden induced subgraphs. We show a dichotomy for the formerproblem restricted to $(H_1,H_2)$-free graphs and a dichotomy for the latterproblem restricted to $H$-free graphs. We find that there exists an infinitefamily of graphs $H$ such that Vertex Steiner Tree is polynomial-time solvablefor $H$-free graphs, whereas there exist only two graphs $H$ for which thisholds for Edge Steiner Tree. We also find that Edge Steiner Tree ispolynomial-time solvable for $(H_1,H_2)$-free graphs if and only if thetreewidth of the class of $(H_1,H_2)$-free graphs is bounded (subject to P$\neq$ NP). To obtain the latter result, we determine all pairs $(H_1,H_2)$ forwhich the class of $(H_1,H_2)$-free graphs has bounded treewidth.

Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective