Algorithms and lower bounds for graph connectivity and covering

Abstract

Graph Connectivity is a well-studied problem, and its time complexity is well understood. However, its space complexity remains a mystery. Closely related to the space complexity of connectivity is the problem of derandomizing space-bounded randomized algorithms that halt after a number of steps exponential in the space bound. We present our results as derandomizations. These results also apply to Graph Connectivity on a related class of graphs. The pseudorandom generator-based approach has been used for derandomizing space-bounded algorithms. We present this approach with new insights, construct a different pseudorandom generator, and prove a related lower bound. We identify a condition such that randomized algorithms satisfying it allow deterministic algorithms with improved space bounds. We study the complexity of a natural Boolean function arising from the pseudorandom generator approach and its impact on derandomizing space-bounded algorithms. We use the results obtained to prove a lower bound for a Boolean function on a restricted computational model. Most Graph Covering problems are known to be NP-hard, and they model many practical problems. We consider two Graph Covering problems: the Graph Editing problem and the Prefix-Free Code Assignment problem. The Graph Editing problem we consider arises from a common challenge in Computational Biology. We present the Prefix-Free Code Assignment problem as an extension of the classical Huffman Coding problem and the Graph Coloring problem. In this work, we present the first hardness results and lower bounds for these problems. We also provide algorithms to solve these problems for special classes of graphs.