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?
The border between P and NP for some problems
complexity theory;np complete;np