Exponential time algorithms via separators and random subsets

Exponential time algorithms for NP-hard problems is rich and diverse research area. This thesis aims to improve known problems with new algorithms and careful analysis of running times by extending on and using known techniques such as graph separators, and random subset selection. We first present a polynomial-space algorithm that computes the number of independent sets of any input graph in time O(1.1389^n) for graphs with maximum degree 3 and in time O(1.2356^n) for general graphs, where n is the number of vertices. Together with the inclusion-exclusion approach of [Björklund, Husfeldt, and Koivisto 2009], this leads to a faster polynomial-space algorithm for the graph coloring problem with running time O(2.2356^n). As a byproduct, we also obtain an exponential-space O(1.2330^n) time algorithm for counting independent sets. We also 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 − 1/c)^n N^O(1), provided that there is an algorithm for the Φ-Extension problem with b^{n−|X|}c^k N^O(1) running time. Here, the input for Φ-Extension is an instance I of size N over a universe UI of size n, a subset X ⊆ U_I , and an integer k, and the task is to check whether there is a set Y with X ⊆ Y ⊆ UI and |Y \ X| ≤ k with property Φ. We also 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 Φ. Lastly we consider the application of random subset selection to approximation algorithms and improve on known approximation algorithms [Escoffier, Paschos and Tourniaire 2016] through a careful application of subset selection, and new analytic methods based on Monotone Local Search. This involves using as sub- routines Fixed Parameter Tractable Algorithms for an exponential time approximation algorithm, and we also investigate using parameterized approximation algorithms for subroutines from [Kulik and Shachnai 2020]