The Study On Relationship And Algorithms For Weighted Edge Packings And Vertex Covers In Bipartite Graphs

Given an undirected graph, a subset of edges is called a matching if no two edges have a vertex in common. A subset of vertices is called a vertex cover if each edge of the graph is incident to at least one vertex of the set. The classical maximum matching problem is to find a matching with the largest number of edges, while the classical minimum vertex cover problem is to find a vertex cover with the least number of vertices. Matching and vertex cover problems are the central problems in combinatorial optimization. In computational complexity theory, the decision version of the matching problem is a typical problem in P Class, and the decision version of vertex cover problem is a typical NP-C problem, and therefore the vertex cover problem can be viewed as a representative of NP-hard optimization problem. The sustained and in-depth study on matching and vertex cover problems has been proved to be very fruitful in the development of combinatorial optimization, from enriching the theory and techniques for the algorithm theory up to establishing some profound mathematical relations. Konig(1931) found that bipartite graphs are the nice structures for matching and vertex cover problems. The classical Konig theorem asserts that in bipartite graphs, the maximum size of a matching is equal to the minimum size of a vertex cover. The development of discrete mathematics has witnessed the power and profoundness of the Konig theorem, as many famous theorems that are fundamental to their disciplines are actually equivalent to the Konig theorem mathematically. They include:the P. Hall theorem in algebra, the Dilworth theorem on Posets, the Menger theorem in graph theory, the max flow min cut theorem in network flow theory, and soon.In this thesix, we are devoted to two generalizations of the classical matching and vertex cover problems, respectively, with a focus on their inter-relationships as well as efficient algorithms for solving them. Given an undirected graph and a non-negative weight function on vertices, a subset of edges (repetition is allowed) is called an edge packing if for each vertex in the graph, the number of edges in F, that are incident to it, is no more than its weight; a subset of vertices is called a vertex cover if it intersects all edges of the graph. The maximum edge packing problem is to find an edge packing with the largest number of edges; and the minimum vertex cover problem is to find a vertex cover with the minimum total weight. These two problems are generalizations of the classical matching and vertex cover problems, and hence are of theoretical and practical importance. In this dissertation, we analyze the computational complexities of these two problems, we formulate integer programming models for them and therefore prove that the optimal values of these two problems are always equal for any non-negative weight function defined on vertices, provided that the graphs given are bipartite graphs, and we design polynomial time algorithms for solving these two problems. Our results generalize the Konig theorem, and could be used as a valuable source for the further study on some packing and covering problems.