Algorithms for NP-hard problems in the sublinear-space regime[HBNI Th209]

Abstract

This thesis is a study on the existence of algorithms for NP-hard problems in the interval of algorithmic complexity between linear and logarithmic space. In the early days, much research was conducted on the existence of logarithmic-space algorithms for polynomial-time problems such as graph reachability, sorting and selection and graph recognition. We show that the region of algorithmic complexity just above logarithmic space is quite rich: one can devise sublinear-space approximation and parameterized algorithms for quite a few NP-hard problems. In recent times, much work has been put into devising ways of dealing with the apparent intractability of NP-hard problems. The two most well-known frameworks developed for this purpose are approximation and parameterization. We consider both these frameworks in the context of sublinear-space algorithms. With regard to approximation, we devise algorithms for the Vertex Cover, d-Hitting Set, Dominating Set, Independent Set and Max r-SAT problems. We also devise parameterized algorithms for the problems ∩s-Hitting Set (a restriction of Hitting Set), Feedback Vertex Set, certain restrictions of the general graph deletion problem Deletion to Π, Min-Ones d-SAT (a generalization of d-Hitting Set), and a number of graph deletion and subgraph search problems parameterized by vertex cover number. To achieve our results, we use tools such as hash families, kernelization, modified greedy strategies and sublinear-space tree decompositions.