The Minimum Connected Vertex Cover Problem On Regular Graphs

Vertex cover is one of the most classical combinatorial optimization problems and is widely used in wireless network design.The so-called connected vertex cover is a vertex cover that can induce a connected sub-graph too.With such further constraint,the minimum connected vertex cover problem remains APX-hard.In this thesis,we focus on the minimum connected vertex cover problem on regular graphs,which has been shown to be NP-hard even on 4-regular graphs.On the one hand,we improve the worst case analysis of an existing algorithm.On the other hand,we design a new approximation algorithm by the local search method.By implementing both algorithms in Python,we succeed to compare them with computational experiments.The full text is divided into four chapters.In the first chapter,we briefly introduce the basic concepts of graph theory,combinatorial optimization problems,computational complexity theory and related definitions on approximation algorithms.In addition,the paper introduces the minimum vertex cover problem and the minimum connected vertex cover problem.It sumarizes the worldwide research on the general graphs and some typical special graphs.Results of computational complexity,exact algorithms,fixed parameter algorithms and approximation algorithms are included.In the second chapter,we devote ourselves to the minimum connected vertex cover problem on 4-and 5-regular graphs.For an existing approximation algorithm that utilizes the greedy approach,we present an improved worst case analysis,where the ratios are improved to 4/3 and 10/7 on 4-and 5-regular graphs,respectively.We also provide instances showing the lower bounds of the algorithm.By simultaneously applying the greedy and the local search approach,Chapter 3 addresses a new approximation algorithm for the minimum connected vertex cover problem on k-regular graphs.Then the new algorithm is implemented through Python and estimated by computational experiments.Finally,we summarize our thesis by observing the further study in the last chapter.