12 Separate, Measure and Conquer in polynomial space
The dynamic programs of Section 11 keep a table for every bag of a path decomposition and therefore use exponential space. In polynomial space the width bounds enter in a different way. A path decomposition of small width contains a small balanced separator, and a branching algorithm can prefer to branch on the vertices of that separator: once the separator is exhausted, the instance falls apart into two independent halves. Gaspers and Sorkin (Gaspers and Sorkin 2017) built a measure-and-conquer analysis around this idea, which they call Separate, Measure and Conquer, and Gaspers and Lee (Gaspers and Lee 2023) used it to count independent sets. In both analyses the separator constant—the coefficient \(\frac16\) of Fomin and Høie (Fomin and Høie 2006)—enters a mathematical program in one or two places. We replace it by \(c_{3}\) and solve the programs again. This gives the following results, all in polynomial space:
Max \((r,2)\)-CSP in time \(r^{0.17935n}\) on cubic instances, \(r^{0.16984m}\) on instances of maximum degree \(4\) and \(r^{0.17587m}\) on all instances, up to \(o(\cdot)\) terms in the exponent, and counting dominating sets of subcubic graphs in time \(O(1.2178^n)\) (Theorem C.3), against the bounds \(r^{n/5}\), \(r^{7m/40}\), \(r^{9m/50}\) and \(O(1.2458^n)\) of Gaspers and Sorkin;
counting independent sets in time \(O(1.1304^n)\) for maximum degree \(3\), in time \(O(1.2037^n)\) for maximum degree \(4\) and \(O(1.2341^n)\) in general, and computing the chromatic number in time \(O(2.2341^n)\) (Theorem C.6), against the bounds \(O(1.1389^n)\), \(O(1.2070^n)\), \(O(1.2356^n)\) and \(O(2.2356^n)\) of Gaspers and Lee.
Appendix C explains the technique, shows where the separator constant enters, and proves both theorems.
Back to top