Abstract: The NP-hard problem in combinatorial optimization has a strong practical engineering application background in many fields such as operations research and management science, and has attracted many scholars to study. The research results have remarkable effects in practical applications, but there are still some areas worth improving. For NP-hard problems in combinatorial optimization, although it is relatively simple in mathematical expression, the difficulty with solving will become extremely difficult with the scale of the problem. Using the traditional exact algorithm to solve the problem, although the optimal solution of the problem can be solved, the solving time is generally intolerable for large-scale problems. Heuristic algorithms are often used to solve large-scale NP-hard problems. However, although heuristic algorithms are fast, they can not obtain the optimal solution of the problem in general, and can only obtain a feasible solution with good quality through many large-scale experiments. However, in general, only an approximate solution can be provided, and the exact solution is required by practical engineering. Therefore, it is of great significance to study the mathematical properties and exact algorithms with low time complexity for such problems, which can not only overcome the shortcomings of existing algorithms, but also provide basic mathematical properties and new research ideas for designing other algorithms.Therefore, starting from the algorithm for the minimum connected vertex cover problem, this paper proposes a reduced-order backtracking algorithm based on the mathematical properties of the problem. By designing the exact algorithm based on the mathematical properties of the problem, it can not only overcome the shortcoming that the heuristic algorithm can not obtain the optimal solution in general cases, but also improve the shortcomings of the traditional exact algorithm for this problem, which has high worst time complexity.
   In addition, studying the general mathematical properties of NP-hard problems and applying the mathematical properties of specific problems to the actual algorithm design can not only provide a strong mathematical basis for the design of lower complexity exact algorithms, but also play a positive role in the design of heuristic algorithms and approximation algorithms with lower time complexity.
   The Minmum Connected Vertex Cover (MCVC) problem is derived from the Minmum Vertex Cover (MVC) problem. The MCVC problem on general graphs is NP-hard. This problem has important application value in the design of wireless network, the arrangement of communication fiber, and the laying of floor electrical lines. To a certain extent, it can not only reduce the resource waste of network line laying and electrical line laying, but also reduce the waste of power resources, and play a role in reducing power loss and improving the utilization efficiency of power resources. The MCVC problem was first proposed by M.R.Garey and D.S.Johnson when they studied the NP-hard problem of rectilinear Steiner tree, which is to find a connected vertex cover set with the minimum number of vertices in a given undirected graph.
   Firstly, this paper studies the mathematical properties of the problem. Some of the mathematical properties can determine whether some vertices are in or not in the minimum connected vertex covering set in batches, so as to reduce the scale of the problem and improve the speed of the accurate algorithm. Secondly, on the basis of mathematical properties, the upper and lower bound sub algorithm, reduced order sub algorithm and backtracking sub algorithm are designed to solve the optimal solution of the problem. Finally, time complexity analysis and examples of wireless network design show that the algorithm can not only obtain the optimal solution of the problem, but also has lower time complexity than the general accurate algorithm.

Key words: minimum connected vertex cover, upper bound sub algorithm, lower bound sub algorithm, backtracking sub algorithm

摘要： 本文从最小连通顶点覆盖问题的求解算法出发,提出一种基于该问题本身的数学性质的降阶回溯算法来求解。通过基于问题的数学性质来设计精确算法,不仅能够克服使用启发式算法求解该问题在一般情形下都无法求得最优解的缺点,也改善了该问题使用传统精确算法时最坏时间复杂度高的缺点。本文首先研究该问题的数学性质,部分数学性质可成批确定某些顶点在或不在最小连通顶点覆盖集中,从而降低该问题的规模,提高精确算法的求解速度。其次,在数学性质的基础上,设计出上下界子算法、降阶子算法、回溯子算法来求解该问题的最优解。最后,时间复杂度分析以及无线网络设计的实例分析表明,该算法不仅能求得该问题的最优解,且相对一般精确算法,本文算法的时间复杂度更低。

关键词: 最小连通顶点覆盖, 上界子算法, 下界子算法, 回溯子算法