Determine whether or not there is a known polynomial$-$time algorithm for solving the problem $($Hamilton Cycle, Travelling salesman problem, Vertex cover, Independent Set, Finding Cliques, Subset Sum, OR Dominating Set$).$

You must justify why there is no known poly$-$time algorithm OR identify a poly$-$time procedure that solves the problem.

$1.$ Graph G is a simple, connected, undirected graph. There are n vertices and m edges. The goal is to color at least k vertices pink, and the remaining n$-$k vertices in green, in such a way that no two pink vertices share an edge. Note that it is possible for two green vertices to share an edge.

$2.$ Graph G is a simple, connected, undirected graph. There are n vertices and m edges The goal is to find at least k vertices that can be colored pink, and the remaining n$-$k vertices that can be colored blue, in such a way that no two pink vertices share an edge, and no two blue vertices share an edge. Note that each vertex must be colored either pink or blue.

$3.$ Graph G is a simple, connected, undirected graph, where each vertex is already assigned one of two colors: pink or blue. The goal is to determine if there is a cycle consisting of only pink vertices.