| VERTEX COVER, INDEPENDENT SET, CLIQUE are three of the original problems shown to be NP-complete by Karp. As fundamental graph-theoretic problems, all three arise in diverse research domains, including computational biology, VLSI design, telecommunications, to name a few. In classical complexity these closely-related problems are considered equivalent in terms of computational difficulty. In parameterized complexity, there exist efficient fixed-parameter algorithms only for the VERTEX C OVER problem, with the other two problems being considered intractable. The research for this thesis will focus on improvements to the state-of-the-art for solving the k-VERTEX COVER problem. Advances made to FPT k-vertex cover algorithms can provide better algorithms for solving the INDEPENDENT S ET and CLIQUE problems, despite their intractability status. We introduce a general parallel framework for FPT k-vertex cover algorithms, and an improved sequential algorithm for graphs of bounded degree. We explore the applicability of this new sequential algorithm for finding a maximum independent set in a graph of bounded degree. We undertake the first investigation of parallel memorization, and develop a time- and space-efficient parallel algorithm for generating the subgraph lookup table. We investigate a variation of the VERTEX COVER problem for bipartite graphs, known as the CONSTRAINED M INIMUM BIPARTITE VERTEX COVER problem. We apply parallel techniques to the current best sequential algorithm, whereby we develop CGM algorithms for the Gallai-Edmonds and Dulmage-Mendelsohn decompositions, both integral components for solving this problem. Finally, we develop both exact and heuristic algorithms for finding maximum cliques. Whenever possible, we supplement our analysis with computational experiments to underscore the effectiveness of our algorithms. |
