Complexity Framework for Forbidden Subgraphs {IV:} The Steiner Forest Problem

Hans L. Bodlaender, Matthew S. Johnson, Barnaby Martin, Jelle Oostveen, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

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. We are motivated by a recent framework that completely characterizes the complexity of many problems on H-subgraphfree graphs. However, in contrast to, e.g. the related Steiner Tree problem, Steiner Forest falls outside this framework. Hence, the complexity of Steiner Forest on H-subgraph-free graphs remained tantalizingly open. We make significant progress on this open problem: our main
results are four novel polynomial-time algorithms for different excluded
graphs H that are central to further understand its complexity. Along
the way, we study the complexity of Steiner Forest for graphs with
a small c-deletion set, that is, a small set X of vertices such that each
component of G−X has size at most c. Using this parameter, we give two
algorithms that we later employ as subroutines. First, we present a significantly faster parameterized algorithm for Steiner Forest parameterized by |X| when c = 1 (i.e. the vertex cover number), which by a recent
result is best possible under ETH [Feldmann and Lampis, arXiv 2024].
Second, we prove that Steiner Forest is polynomial-time solvable for
graphs with a 2-deletion set of size at most 2. The latter result is tight,
as the problem is NP-complete for graphs with a 3-deletion set of size 2.
Original languageEnglish
Title of host publicationCombinatorial Algorithms - 35th International Workshop, IWOCA 2024, Ischia, Italy, July 1-3, 2024, Proceedings
PublisherSpringer
Pages206-217
ISBN (Electronic)978-3-031-63021-7
ISBN (Print)978-3-031-63020-0
DOIs
Publication statusPublished - 22 Jun 2024

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume14764

Fingerprint

Dive into the research topics of 'Complexity Framework for Forbidden Subgraphs {IV:} The Steiner Forest Problem'. Together they form a unique fingerprint.

Cite this