Faster exponential algorithms for cut problems via geometric data structures

László Kozma, Junqi Tan

For many hard computational problems, simple algorithms that run in time $2^n\cdot n^{O(1)}$ arise, say, from enumerating all subsets of a size-$n$ set. Finding (exponentially) fa…