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?

  • $\begingroup$ I don’t think such problems have a name. $\endgroup$ May 3, 2020 at 22:31

1 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.

  • $\begingroup$ Thank you for your reply. Do you have some references? $\endgroup$
    – melfnt
    May 3, 2020 at 8:14
  • $\begingroup$ @melfnt: Adding references for all these is quite a lot of effort. Most of them can probably be found on Wikipedia and similar pages. I suggest that you look for them yourself there, and fill in the ones that you can find, and perhaps the OP can add any that are left over. $\endgroup$ May 3, 2020 at 13:32
  • $\begingroup$ I agree, I meant references on this kind of problems or phenomena $\endgroup$
    – melfnt
    May 3, 2020 at 13:36
  • $\begingroup$ I don't have references to this kind of problems. But I have added some references to the specific problems I listed in my answer. $\endgroup$
    – Steven
    May 3, 2020 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.