Vertex Cover Search Trees
- PDF / 163,672 Bytes
- 3 Pages / 547.087 x 737.008 pts Page_size
- 25 Downloads / 171 Views
V
Vertex Cover Preprocessing
Vertex Cover Preprocessing Vertex Cover Kernelization
Vertex Cover Search Trees 2001; Chen, Kanj, Jia JIANER CHEN Department of Computer Science, Texas A&M University, College Station, TX, USA Keywords and Synonyms Branch and search; Branch and bound Problem Definition The VERTEX COVER problem is one of the six “basic” NPcomplete problems according to Garey and Johnson [7]. Therefore, the problem cannot be solved in polynomial time unless P = NP. However, the NP-completeness of the problem does not obviate the need for solving it because of its fundamental importance and wide applications. One approach is to develop parameterized algorithms for the problem, with the computational complexity of the algorithms being measured in terms of both input size and a parameter value. This approach was initiated based on the observation that in many applications, the instances of the problem are associated with a small parameter. Therefore, by taking the advantages of the small parameters, one may be able to solve this NP-complete problem effectively and practically. The problem is formally defined as follows. Let G be an (undirected) graph. A subset C of vertices in G is a vertex cover for G if every edge in G has at least one end in C. An instance of the (parameterized) VERTEX COVER problem consists of a pair (G, k), where G is a graph and k is an integer (the parameter), which is to determine whether the graph G has a vertex cover of k vertices. The goal is to develop parameterized algorithms of running time O(f (k)p(n)) for the VERTEX COVER problem, where p(n) is a lower-degree polynomial of the input size n, and f (k) is the non-polynomial part that is a function of the parameter k but independent of the input size n. It would be expected that the non-polynomial function f (k) is as small as possible. Such an algorithm would become “practically effective” when the parameter value k is small. It should be pointed out that unless an unlikely consequence occurs in complexity theory, the function f (k) is at least an exponential function of the parameter k [8].
Key Results A number of techniques have been proposed in the development of parameterized algorithms for the VERTEX COVER problem. Kernelization Suppose (G, k) is an instance for the VERTEX COVER problem, where G is a graph and k is the parameter. The kernelization operation applies a polynomial time preprocessing on the instance (G, k) to construct another instance (G0 , k0 ), where G0 is a smaller graph (the kernel) and k 0 k, such that G0 has a vertex cover of k0 vertices if and only if G has a vertex cover of k vertices. Based on a classical result by Nemhauser and Trotter [9], the following kernelization result was derived. Theorem 1 There is an algorithm of running time O(kn + k 3 ) that for a given instance (G, k) for the VERTEX COVER problem, constructs another instance (G0 , k0 ) for the problem, where the graph G0 contains at most 2k0 vertices and k 0 k, such that the graph G has a vertex cover of k vertices if and only if
Data Loading...
