Abstract We present a polynomial-space algorithm that computes the number of independent sets of any input graph in time $$O(1.1389^n)$$ O ( 1 . 1389 n ) for graphs with maximum degree 3 and in time $$O(1.2356^n)$$ O ( 1 . 2356 n ) for general graphs, where n is the number of vertices in the input graph. Together with the inclusion-exclusion approach of Björklund, Husfeldt, and Koivisto [SIAM J. Comput. 2009], this leads to a faster polynomial-space algorithm for the graph coloring problem with running time $$O(2.2356^n)$$ O ( 2 . 2356 n ) as well as an exponential-space $$O(1.2330^n)$$ O ( 1 . 2330 n ) time algorithm for counting independent sets. Our main algorithm counts independent sets in graphs with maximum degree at most 3 and no vertex with three neighbors of degree 3. This polynomial-space algorithm is designed and analyzed using the recently introduced Separate, Measure and Conquer approach [Gaspers & Sorkin, ICALP 2015]. Using Wahlström’s compound measure approach, this improvement in running time for small degree graphs is then bootstrapped to larger degrees, giving the improvement for general graphs. Combining both approaches leads to some inflexibility in choosing vertices to branch on for the small-degree cases, which we counter by structural graph properties.

We consider the family of $Φ$-Subset problems, where the input consists of an instance $I$ of size $N$ over a universe $U_I$ of size $n$ and the task is to check whether the universe contains a subset with property $Φ$ (e.g., $Φ$ could be the property of being a feedback vertex set for the input graph of size at most $k$). Our main tool is a simple randomized algorithm which solves $Φ$-Subset in time $(1+b-\frac{1}{c})^n N^{O(1)}$, provided that there is an algorithm for the $Φ$-Extension problem with running time $b^{n-|X|} c^k N^{O(1)}$. Here, the input for $Φ$-Extension is an instance $I$ of size $N$ over a universe $U_I$ of size $n$, a subset $X\subseteq U_I$, and an integer $k$, and the task is to check whether there is a set $Y$ with $X\subseteq Y \subseteq U_I$ and $|Y\setminus X|\le k$ with property $Φ$. We derandomize this algorithm at the cost of increasing the running time by a subexponential factor in $n$, and we adapt it to the enumeration setting where we need to enumerate all subsets of the universe with property $Φ$. This generalizes the results of Fomin et al. [STOC 2016] who proved the case where $b=1$. As case studies, we use these results to design faster deterministic algorithms for: - checking whether a graph has a feedback vertex set of size at most $k$ - enumerating all minimal feedback vertex sets - enumerating all minimal vertex covers of size at most $k$, and - enumerating all minimal 3-hitting sets. We obtain these results by deriving new $b^{n-|X|} c^k N^{O(1)}$-time algorithms for the corresponding $Φ$-Extension problems (or enumeration variant). In some cases, this is done by adapting the analysis of an existing algorithm, or in other cases by designing a new algorithm. Our analyses are based on Measure and Conquer, but the value to minimize, $1+b-\frac{1}{c}$, is unconventional and requires non-convex optimization.