The Maximum Colorful Independent Set In Vertex-colored Bipartite Graph

The paper mainly study the maximum colorful independent set(MCISP for short)in vertex-colored bipartite graph.This problem can be described as follows,for any given vertex-colored bipartite graph,regardless of the way coloring vertex,we try to find the independent set containing maximum color in this graph.General MCISP is NP-hard in bipartite graph,this paper first designs approximation algorithms for this NP-hard prob-lem,and proves NP-hard and offers two polynomial approximation algorithms for the problems in which the occurrence of color is restricted,specific content in each chapter in this paper are as follows.In the first chapter,we primarily introduce the basic concept of graph theory and the definition of computational complexity,and discuss approximation algorithms,boolean satisfiability problem(SAT for short),vertex-colored graph,and independent set problem.In the second chapter,we design approximation algorithms with worst case ratio of2 in a general bipartite graph,which finds an independent set containing maximum color using the quality of independent set in bipartite graph,then for special NP-hard situations where the occurrence of each color in vertex restricted to 3 in the complete bipartite blocks,we give the worst case of₃⁴based on greedy idea.In the third chapter,the quality of NP-hard is proved in claw-free graph,P₆-free graph and fork-free graph with balanced MAX-(3,B2)-SAT and MAX-2SAT,which ex-plained MCISP is still NP-hard for the complete bipartite blocks where the occurrence of color in vertex is restricted to 2.So we study the approximation algorithms in this situation,the approximation ratio of₂³based on greedy idea is proposed.Consequently,we improve this algorithm and propose the worst case of₃⁴.The fourth chapter concludes the full content and gives the analysis and prospects for the ongoing research.