Problems for which a small change in the statement causes a big change in time complexity

Question

I know that there are several problems for which a small change in the problem statement would result in a big change in its (time) complexity, or even in its computability.

An example: The Hamiltonian path problem defined as

Given a graph, determine whether a path that visits each vertex exactly once exists or not.

is NP-Complete while the Eulerian path problem defined as

Given a graph, determine whether a trail that visits every edge exactly once exists or not.

is solvable in linear time with respect to the number of edges and nodes of the graph.

Another example is 2-SAT (polynomial complexity) vs K-SAT (NP-complete) although someone could argue that 2-SAT is just a specific case of K-SAT.

What do you call this kind of problems --if they even have a name? Can someone provide a list of other examples or some references?

Answer 1

• Given a graph, does it have a cycle of length $3$ ($4$)? Four-cycles there is an easy algorithm that requires $O(n^2)$ time. The best known algorithm for triangle detection is related to matrix multiplication and has complexity $O(n^\omega)$ where $\omega$ is the matrix multiplication exponent. It is an open problem to determine whether $\omega=2$.

• Given a graph, decide if its vertices can be colored with 2 (3) colors. Two colors: it is equivalent to testing the graph for bipartiteness, Three colors: NP-Complete.

• Given a graph, decide if its edges be colored with 2 (3) colors. Two colors: trivial (color an first edge arbitrarily, follow all implied edges, repeat). Three colors: NP-Complete.

• Given a system of Diophantine equations, does it a admit a (non-negative) solution? Solvable in polynomial time if variables can be negative, NP-Complete otherwise.

• Given a graph and two vertices $s$ and $t$, what is the length of the shortest (longest) path between $s$ and $t$? Shortest path: essentially a BFS. Longest path: NP-hard.

• A lot of graph problems that are hard in general, are easy on trees (vertex cover, independent set, dominating set, ...). See Kleinberg & Tardos, perfect graphs, and notice that a minimum dominating set on a tree can be found by greedily selecting a parent $v$ of a leaf, deleting $v$ and its neighbors, and repeating.

• Given a directed graph, can you partition its edges into paths of length 2 (1)? For paths of length 1 the problem is trivial. For length 2 there it is a generalization of 3-dimensional-matching.

• Given a set of numbers, can it be partitioned into groups of 2 (3) elements so that all groups have the same sum? For groups of two elements it is trivial (the match of an element is completely determined by the element itself). For groups of $3$ it is the 3-partition problem.

• Given a NFA, does it accept (reject) at least one word? Accept: this boils down to a connectivity check between the initial state and the final states. Reject: PSPACE-Complete (search Universality problem).

• Given a graph $G$, two vertices $s$ and $t$, and $c \in \mathbb{N}$. Does $G$ contain $4$ ($5$) edge disjoint paths of length at most $c$? For 4 paths the problem is solvable in polynomial time, for 5 paths it is NP-hard.

• Given an edge-weighted graph $G$ and two vertices $s$ and $t$, what is the minimum (maximum) weight of a $s$-$t$ cut in $G$? See minimum-cut (polynomial) and maximum-cut (NP-hard).

• Given a set of linear constraints, is there at least one (integral) point in their intersection? Solvable in polynomial-time if variables are not restricted to be integers, otherwise NP-hard.