Complexity framework for forbidden subgraphs IV: The Steiner Forest problem

Journal of Computer and System Sciences, vol. 154, pp. 103682

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. In contrast to the related Steiner Tree problem, Steiner Forest falls outside a recent framework that completely characterizes the complexity of many problems on H -subgraph-free graphs. Hence, the complexity of Steiner Forest on H -subgraph-free graphs remained open. Our main results are four polynomial-time algorithms for different excluded graphs H that are central to further understand its complexity. We also 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 connected component of G − X has size at most c . For this parameter, we give two algorithms that we later employ as subroutines (including a faster algorithm when c = 1 , that is, the vertex cover number) and exhibit a dichotomy theorem.

Authors 8

1. Hans L. Bodlaender

   Utrecht University

   Affiliation as printed

   Department of Information and Computing Sciences, Utrecht University, Princetonplein 5, 3584 GT, Utrecht, the Netherlands

2. Matthew Johnson

   Durham University

   Affiliation as printed

   Department of Computer Science, Durham University, Stockton Road, DH1 3LE, Durham, United Kingdom

3. Barnaby D. Martin

   Durham University

   Affiliation as printed

   Department of Computer Science, Durham University, Stockton Road, DH1 3LE, Durham, United Kingdom

4. Jelle J. Oostveen

   Utrecht University

   Affiliation as printed

   Department of Information and Computing Sciences, Utrecht University, Princetonplein 5, 3584 GT, Utrecht, the Netherlands

5. Sukanya Pandey Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen, Ahornstrasse 55, E1, 52074, Aachen, Germany

6. Daniël Paulusma

   Durham University

   Affiliation as printed

   Department of Computer Science, Durham University, Stockton Road, DH1 3LE, Durham, United Kingdom

7. Siani Smith

   Loughborough University

   Affiliation as printed

   Department of Computer Science, Loughborough University, LE11 3TU, Loughborough, United Kingdom

8. Erik Jan van Leeuwen corresponding

   Utrecht University

   Affiliation as printed

   Department of Information and Computing Sciences, Utrecht University, Princetonplein 5, 3584 GT, Utrecht, the Netherlands