Fast Polynomial-Space Algorithms Using Inclusion-Exclusion

Given a graph with n vertices, k terminals and positive integer weights not larger than c, we compute a minimum Steiner Tree in ${𝒪}^{\star }(2^{k}c)$ time and ${𝒪}^{\star }(c)$ space, where the ${𝒪}^{\star }$ notation omits terms bounded by a polynomial in the input‐size. We obtain the result by defining a generalization of walks, called branching walks, and combining it with the Inclusion‐Exclusion technique. Using this combination we also give ${𝒪}^{\star }(2^n)$ ‐time polynomial space algorithms for Degree Constrained Spanning Tree, Maximum Internal Spanning Tree and #Spanning Forest with a given number of components. Furthermore, using related techniques, we also present new polynomial space algorithms for computing the Cover Polynomial of a graph, Convex Tree Coloring and counting the number of perfect matchings of a graph.