Complexity framework for forbidden subgraphs IV: The Steiner Forest problem

We study STEINER FOREST on H-subgraph-free graphs, that is, graphs that do not contain some fixed graph H as a (not necessarily induced) subgraph. In contrast to the related STEINER TREE problem, STEINER FOREST falls outside a recent framework that completely characterizes the complexity of many pro...

Full description

Saved in:
Bibliographic Details
Main Authors: Hans L. Bodlaender, Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Format: Default Article
Published: 2025
Subjects:
Information and computing sciences
Distributed computing and systems software
Information systems
Theory of computation
Mathematical sciences
Steiner Forest
Forbidden subgraph
Complexity dichotomy
Vertex cover number
Deletion set
Online Access:https://hdl.handle.net/2134/31017625.v1
Tags: Add Tag
No Tags, Be the first to tag this record!

Similar Items