A problem is defined to be in NP when it can be reduced to another NP problem in polynomial time.
In Karp's 21 NP-complete problems, the most famous ones are presented. However, I wonder (and could not find a reference) for some of them, what happens if we "relax" the objective function.
For instance, say Hamiltonian path problem: given a graph $G$ with $n$ vertices, is there a simple path $P$ of length $n$? (i.e. passes through all vertices). This problem is NP-complete.
But what if I ask for a path $P$ whose length is $n-k$? At which value of $k$ the problem becomes tractable?
Similarly, 3-coloring problem: color the vertices of a graph with three colors such that no two adjacent vertices have the same color. What if I allow $k$ pairs of adjacent vertices to be the same color?
Is this descripton the very same thing with approximation algorithms? Or is this a different concept?