Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes. A $k$-caterpillar is a tree formed from main path by growing edge-disjoint paths of length at most $k$ from its nodes ($k$ is called the hair length). Minimum Bandwidth problem is in $P$ for 2-caterpillars but it is $NP$-complete for 3-caterpillars. Here is a very interesting fact, Minimum bandwidth problem is solvable in polynomial time for 1-caterpillars (hair length at most one) but it is $NP$-complete for cyclic 1-caterpillars (in cyclic caterpillar, one edge is added to connect the endpoints of the main path). So, the addition of exactly one edge makes the problem $NP$-complete.What is the most striking example of problem hardness jump where a small variation of input instance causes a complexity jump from polynomial-time solvability to $NP$-completeness?
Hardness jumps in computational complexity?
cc.complexity theory
One of the more interesting applied examples of hardness jumps can be observed in the following problem:Consider a soccer league championship with $n$ teams: The problem of deciding whether a given team can (still) win the league is in $P$ if in a match, the winning team is awarded 2 points, the losing one 0 and each team is awarded 1 point in a draw match. But if we change the rules so that the winning team gets 3 points, the same problem becomes $NP$-hard. The result can be generalized for any $(0, 1, k)$-point rule for every $k > 2$ and even for only three remaining rounds.Source: Complexity Theory by Ingo Wegener (http://portal.acm.org/citation.cfm?id=1076319)