The Algorithms And Complexity Of The Maximum Internal Spanning Tree Problem

Computational problems are a set of mathematical problems that can be solved by computers. For example, primality testing which is to decide whether a given integer is a prime is a classical computational problem. A computational problem can be described by giving:(1) a general description of all its parameters, and (2) a statement of what properties the answer, or solution,is required to satisfy. Such a statement is referred to as a question of the problem. An instance of a problem is obtained by specifying particular values for all the problem parameters. As an example, consider the primality testing problem. The instance of the problem is a given integer, and the question is to decide whether the integer is a prime.In this thesis we mainly treat with two kinds of computational problems which are decision problems and functional problems. The main difference between these two kinds is the description of their answers to their questions. The decision problems only need to give a "Yes" or "No" answer, while the functional problems have more complex answers. The answers to the functional problems are not just "Yes" or "No". They may be a string or a mathematical number. For example, the primality testing problem is a decision prob-lem, while the travelling salesman problem is a classical functional problem. Searching problems are a set of functional problems. An answer to a searching problem can be an arbitrary string. For example, the problem of finding a spanning tree for a given graph is a searching problem. One just need to present an arbitrary spanning tree for the graph. However, usually people not only need a spanning tree but also except to find a spanning tree with some parameter "best", such as a spanning tree with its maximum degree mini-mized. This is the so called optimization problem. An optimization problem is to find an "optimal solution" among all possible solutions to a searching problem.Researchers pay more attentions to decision problems and optimization problems. Researchers hope to present an efficient method to find an answer to a problem. A method is said to be efficient if the time needed to solve a problem grows not very fast with the growing of this problem instance scale. From computer researchers’viewpoint, an efficient method can solve a problem in polynomial time. However, a lot of problems, no matter whether they are decision problems or optimization problems, are hard to find an efficient method to solve them. NP-hard problems is such a kind of problems.People extensively consider optimization problems which are NP-hard. Although it is hard to find an efficient method to find an optimal solution for such an optimization problem, researchers try to find a feasible solution whose value is as close as possible to the value to an optimal solution. This is the idea of approximation algorithms. Approx-imation algorithms can identify the difference between the value to the feasible solution obtained by the algorithm and the value to an optimal solution, so approximation algo-rithms are some researchers’ favorites.The decision problems which are NP-hard are a little tricker to solve. The decision problems only need to answer "Yes" or "No", and it is hard to find an efficient method to give answers to these problems. So there seems to be the only way that one must find a method with the time complexity as low as possible. However, inspired by approximation algorithms, researchers can find another way out. Researchers find that some NP-hard decision problems can be transformed into their corresponding optimization versions with the condition that the answer to some instance of a decision problem is "Yes" if and only if an optimal solution to the instance of the decision problem’s corresponding optimization problem is a "Yes" witness to the answer to the instance of the decision problem. Such a transformation is to generalize a decision problem. When considering a generalized decision problem, one may find some useful properties for the decision problem. As an example, MaxSAT problem is a generalized SAT problem, because a conjunctive normal form is satisfied if and only if the optimal solution of its corresponding optimization problem can satisfy all clauses.We consider another NP-hard decision problem-Hamilton path problem. Hamilton path problem asks to find a simple path to cover all vertices for an undirected simple graph. There are a lot of generalized Hamilton path problems which are also optimiza-tion problems, such as Maximum Internal Spanning Tree problem, Minimum Branching Spanning Tree problem, Minimum Leaves Spanning Tree problem and Path Cover prob-lem. In this thesis, we study the Maximum Internal Spanning Tree problem and the Path Cover problem. We try to design approximation algorithms and study the inapproxibility for these two problems. The contributions in this thesis are as following.1, Approximating the Path Cover problemFor an undirected simple graph, the Path Cover problem asks to find a set of vertex-disjoint paths to cover all vertices of the graph. For an undirected simple graph, an optimal solution to the Path Cover problem has only one path if and only if this graph has a Hamilton path, so the Path Cover problem is a generalized version of the Hamilton Path problem. We present a new upper bound for the number of edges in a feasible solution of the Path Cover problem, and propose a new approximation algorithm. Using this upper bound, we prove that the approximation ratio of the algorithm is 10/7. Finally we prove that the Path Cover problem is APX-hard, which means that there is no polynomial time approximation scheme(PTAS) to solve this problem unless P= NP.2, Approximating the Maximum Internal Spanning Tree problemThe Maximum Internal Spanning Tree problem asks to find a spanning tree with the maximum number of internal vertices among all spanning trees in a graph. For an undirected simple graph, an optimal solution of the Maximum Internal Spanning Tree problem is a simple path if and only if the given graph has a Hamilton path, so this problem is also a generalized version of the Hamilton Path problem. Inspired by the research of the Path Cover problem, we prove that the number of internal vertices in a spanning tree of a graph is less than the number of edges in an optimal solution of the Path Cover problem. Moreover, the number of edges in an optimal solution of the Path cover problem for a graph is less than that in a maximum path-cycle cover of this graph. So the number of internal vertices in a spanning tree of a graph is less than the number of edges in a maximum path-cycle cover of this graph. Based on this upper bound, we present a 1.5-approximation algorithm for this problem, and then improve the performance to 4/3. This result is the best by now. Finally we prove that the Maximum Internal Spanning Tree problem is APX-hard.The author present the following possible directions for the future work.1, Randomized approximation technique has been a hot technique to design algo-rithms recent years. Through our research, we find that it is easy to design an algorithm with performance ratio very close to 1 in most cases for the Path Cover problem. So we guess that there may be a randomized approximation algorithm with expected approxi-mation ratio very close to 1 to solve the Path Cover problem.2, There are two possible sides to improve the performance ratio for the Maximum Internal Spanning Tree problem.The first one is to follow our idea. The barrier to improve the performance ratio is those path components of length four and those cycle components of length four in a maximum path-cycle cover. If either of these two connected components has a large enough amount, then the performance ratio of our algorithm stays at4/3|. So if one could present an upper bound on the number of internal vertices which are contributed to a spanning tree by the path components of length four and the cycle components of length four in a maximum path-cycle cover, then it will be easy to improve our algorithm.The second direction is to use local optimization technique. Jianer Chen has already present a 1.5-approximation algorithm for this problem by a local search technique in which it starts with an arbitrary spanning tree. We guess that there must be a local search algorithm with better performance ratio than 4/3 if the algorithm starts with a spanning tree output by the 4/3-approximation algorithm.3, It is still significant to decide a constant factor that the Path Cover problem and the Maximum Internal Spanning Tree problem can not approximate to respectively, although this thesis has already proved that both of them are APX-hard.