Generally, a graph G, an independent set is a subset S of vertices in G such
that no two vertices in S are adjacent (connected by an edge) and a vertex
cover is a subset S of vertices such that each edge of G has at least one of
its endpoints in S. Again, the minimum vertex cover problem is to find a vertex
cover with the smallest number of vertices. This study shows that the
constrained minimum vertex cover problem in k-partite graph (MIN CVCK) is
NP-Complete which is an important property of k partite graph. Many
combinatorial problems on general graphs are NP-complete, but when restricted
to k partite graph with at most k vertices then many of these problems can be
solved in polynomial time. This paper also illustrates an approximation
algorithm for MIN CVCK and analyzes its complexity. In future work section, we
specified a number of dimensions which may be interesting for the researchers
such as developing algorithm for maximum matching and polynomial algorithm for
constructing k-partite graph from general graph.