Research on Solution Space of Bipartite Graph Vertex-Cover by Maximum Matchings

Some algorithms and statistics of the vertex-cover solution space on bipartite graphs are investigated in this paper. Based on 's theorem, an exact algorithm for solution space expression is proposed and some statistical analysis of the nodes' states is provided. The statistical results fit well with the algorithmic ones before the emergence of the unfrozen core, which leads to fluctuations of the statistical quantities and produces replica symmetric breaking in the solutions. Besides, the entropy and the clustering entropy of bipartite-graph vertex-cover solutions are calculated using some cycle simplification technique for the unfrozen core. Furthermore, as a generalization of bipartite graphs, a bipartite core graph is proposed, the solution space of which can also be easily determined; and to have further knowledge on the easily-solving vertex-cover instances, how to generate a – subgraph is studied by a growth process of adding edges. The investigation on the solution space of a bipartite-graph vertex-cover provides some insights and intensive understanding on solution space complexity, and will provide benefits in finding the maximum – subgraphs, solving a general-graph vertex-cover and recognizing the intrinsic hardness of NP-complete problems.