Vertex cover: Exact and approximation algorithms and applications

Many optimization problems from industrial applications are NP-hard. According to the NP-completeness theory, these problems cannot be solved in polynomial time unless P = NP. However, this fact does not obviate the need for solving these problems for their practical importance.; An outstanding example of such optimization problems is the well-known NP-hard problem Vertex Cover. This problem has numerous applications in fields like biochemistry, VLSI design, and networking.; In this dissertation, we study exact and approximation algorithms for the Vertex Cover problem and their applications. First we develop new properties for Vertex Cover and introduce several simple and new techniques that lead to an exact parameterized algorithm of time O(kn + 1.285kk2) for the problem. This algorithm is an improvement over previous algorithms for Vertex Cover. It also induces improvements on previous algorithms for the Independent Set problem on low-degree graphs.; Next we consider the constrained minimum vertex cover problem on bipartite graphs, shortly Min-CVCB. We give a formal proof to show that Min-CVCB is NP-complete. Then we develop an exact parameterized algorithm for the problem of running time $O1.26ku+kl+ku+kln$, where k_u and k_l are the given parameters. The algorithm is a significant improvement over previous algorithms for the Min-CVCB problem.; After studying exact algorithms for the Vertex Cover and the Min-CVCB problems, we turn our attention to studying the approximability of the Minimum Vertex Cover problem. It has become an outstanding open problem whether there is a polynomial time approximation algorithm for Minimum Vertex Cover whose approximation ratio is bounded by a constant less than 2. We consider the approximability of Minimum Vertex Cover on graphs with perfect matching (VC-PM). We show that if the VC-PM problem has a polynomial time approximation algorithm with ratio bounded by a constant less than 2, then so does the Minimum Vertex Cover problem on general graphs. Approximation algorithms for VC-PM are then developed, which induce improvements over previously known algorithms on sparse graphs.; The dissertation concludes with discussions on some scientific and industrial applications of our algorithms. We also give pointers to some directions along which the current research can be extended.