34
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ Permanent vs Determinant. These are two different problems(so I guess it doesn't qualify as an answer) but the hardness jump is quite striking. $\endgroup$ – Jagadish Oct 26 '10 at 6:56
  • $\begingroup$ @Jagadish, I agree. Still, I think you can post it as answer. $\endgroup$ – Mohammad Al-Turkistany Oct 26 '10 at 7:35
  • 8
    $\begingroup$ Permanent of a 0-1 matrix can be seen as the expected value of the determinant of the matrix when the 1 entries are replaced by +1 or -1 at random. $\endgroup$ – Dana Moshkovitz Nov 7 '10 at 1:31
  • $\begingroup$ @Dana, Could you please make your comment a separate answer? (preferably with a reference) $\endgroup$ – Mohammad Al-Turkistany Dec 5 '10 at 9:01
  • $\begingroup$ Community Wiki? $\endgroup$ – Niel de Beaudrap Apr 29 '13 at 22:46

17 Answers 17

46
$\begingroup$

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)

$\endgroup$
  • 12
    $\begingroup$ this reminds me of TSP: you can get a 1.5 approx with weights that are 1 or 2, but not if weights are 1 or 3 $\endgroup$ – Suresh Venkat Nov 5 '10 at 20:06
24
$\begingroup$

This answers the question asked in the question-title, but not the one asked in the question.

A shocking example of jump-in-hardness arises from the question, "How many satisfying assignments does a planar formula have, modulo $n$?" This was widely thought to be #P-hard, and it is for "most" values of $n$, but if $n$ is a Mersenne integer (for example $n=7$, because 7 is of form $2^3-1$), then the answer can be computed in polynomial time.

This was first discovered by Valiant, in his groundbreaking Holographic Algorithms paper.

$\endgroup$
  • 4
    $\begingroup$ That is not quite right. The formula doesn't just need to be planar. It also needs to be monotone, read-twice, and have size $k$ clauses, where $n = 2^k - 1$. Valiant's presentation in Holographic Algorithms is to fix clause size to $k=3$ and then vary the modulus. Characteristic 0 hardness (i.e. #P-harness) was known. Valiant proved hardness mod 2 and tractable mod 7. Note that this hardness is $\oplus P = \#_2 P$ hardness, not #P-hardness. I believe the complexity mod other values is open. Later, Jin-Yi Cai and Pinyan Lu gave tractability for all $k$. $\endgroup$ – Tyson Williams Dec 13 '13 at 4:25
  • 2
    $\begingroup$ For more on this, including the paper references, see Holographic_algorithm#History on Wikipedia. $\endgroup$ – Tyson Williams Dec 13 '13 at 4:27
21
$\begingroup$

INDEPENDENT SET is NP-complete for (cross,triangle)-free graphs, but can be solved in linear time for (chair,triangle)-free graphs. (The X-free graphs are those that contain no graph from X as an induced subgraph.)

chair: image of chair graph from ISGCI triangle: image of triangle graph from ISGCI cross: image of cross graph from ISGCI

Notice that the cross is obtained from the chair by adding a single edge.

$\endgroup$
  • 12
    $\begingroup$ What about this more simple example: INDEPENDENT SET is NP-c for $K_{1,4}$-free graphs, but can be solved in linear time for $K_{1,3}$-free (i.e., claw-free) graphs. $\endgroup$ – vb le Apr 29 '13 at 19:23
19
$\begingroup$

I am not sure I would go along with your characterization that adding a single edge to the input makes the problem NP-complete, since one is actually allowing an edge to be added to every one of the infinitely many input instances.

Here is an example of a problem which shows a sharp dichotomy along the lines you suggest.

The problem of determining whether there is a graph homomorphism from the input graph G to a fixed template graph H is in P when H is a graph with a self-loop or is a bipartite loopless graph. When H is not bipartite (this can often be achieved by adding a single edge) then the problem becomes NP-complete.

The key here is that 2-colouring is in P (this corresponds to a homomorphism to $P_3$, the path on 3 vertices), while 3-colouring is NP-complete (this corresponds to a homomorphism to $K_3$, the triangle).

$\endgroup$
14
$\begingroup$

Here's another interesting example, raised in induced subgraph detection:

A theta is a graph with non-adjacent vertices $x,y$, three paths $P_1, P_2, P_3$ from $x$ to $y$, where any two paths induced a cycle with length greater than 3.

A pyramid is a graph with a vertex $x$, a triangle $y_1,y_2,y_3$, and paths $P_i$ from $x$ to $y_i$ for each $i=1,2,3$, with at most one path with length one.

Finally, a prism is a graph with two triangle $x_1,x_2,x_3$ and $y_1,y_2,y_3$, and paths $P_i$ from $x_i$ to $y_i$ for each $i=1,2,3$.

It is easy to describe in figures:

theta, prism and pyramid

For detecting induced theta and pyramid, it is known to be in polynomial time. (In fact, the best known algorithm for theta takes $O(n^{11})$ time, and for pyramid it takes $O(n^9)$.) But for detecting an induced prism, the problem becomes NP-hard.

One can see "Detecting induced subgraphs" by Leveque, Lin, Maffray and Trotignon for reference. The reason that theta and pyramid are relatively easy is related to the "three-in-a-tree" problem, described in "The three-in-a-tree problem" by Chudnovsky and Seymour.

$\endgroup$
13
$\begingroup$

er ... i'm sure you're looking for less trivial examples... but I would like to point out that there's something special about the number $2$ vs $3$. $2-SAT$ to $3-SAT$, $2-COL$ vs $3-COL$, etc. Intuitively, I've always figured it was because a node with at most 2 edges can form at most a line, but a node with 3 edges can form a tree, when we move from 2-3 we get a combinatorial explosion.

$\endgroup$
  • 9
    $\begingroup$ on the other hand, MAX 2SAT is hard. so 2 isn't THAT special. $\endgroup$ – Suresh Venkat Oct 25 '10 at 7:43
  • 1
    $\begingroup$ 2 AND perfect completeness seem special though. :) $\endgroup$ – Daniel Apon Nov 5 '10 at 15:36
  • $\begingroup$ Also, 2D perfect matching vs 3D perfect matching. $\endgroup$ – Mohammad Al-Turkistany Nov 5 '10 at 19:57
13
$\begingroup$

I think that it does not make much sense to talk about instances. We can talk about two distribution of input instances with different difficulties, but it would be more interesting if there is relation between the distribution, or between instances in the distributions.

We can consider a parameterized family of distributions, and then talk about what happens when we change the parameter. You might be interested in what is called the threshold phenomenon, "where a system undergoes a swift qualitative change as a result of a small change in a parameter ...". Take a look at this survey: Ehud Friedgut, "Hunting for Sharp Thresholds", Random Structures Algorithms 26, 2005.

I think one of the most striking and beautiful examples is the random k-SAT with clause density $\Delta$, the phase transition is really amazing.

$\endgroup$
11
$\begingroup$

Inferring types for lambda terms is DEXPTIME-complete with prenex and rank-2 polymorphic type systems (when type quantifiers are nested at most one level deep), but becomes undecidable for rank-3 and higher. Strange that one extra nesting level can render a problem undecidable.

$\endgroup$
10
$\begingroup$

Finding ground state of planar Ising model with 0 magnetic field is in P, with non-zero magnetic field it is NP-hard. Partition function of planar Ising model with 0 magnetic field is in P, with non-zero magnetic field it is NP-hard.

$\endgroup$
9
$\begingroup$

Here is a nice problem with an interesting complexity jump like Minimum Bandwidth you addressed in your question.

Let $G$ be a graph and $T$ a spanning tree of $G$. The detour for an edge $uv\in E(G)$ is the unique $u$-$v$ path in $T$. The congestion of $e \in E(T)$, denoted by $\mathrm{cng}_{G,T}(e)$ is the number of detours that contain $e$. The congestion of $G$ in $T$, denoted by $\mathrm{cng}_G(T)$, is the maximum congestion over all edges in $T$. The spanning tree congestion of $G$, denoted by $\mathrm{stc}(G)$, is the minimum congestion over all spanning trees of $G$. The Spanning Tree Congestion problem asks whether a given graph has spanning tree congestion at most some given $k$.

The following complexity jump is shown in: Bodlaender et al., Parameterized Complexity of the Spanning Tree Congestion Problem, Algorithmica 64 (2012) 85–111:

For every fixed $k$ and $d$ the problem is solvable in linear time for graphs of degree at most $d$. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes $\mathsf{NP}$-complete for any fixed $k\ge 8$.

$\endgroup$
8
$\begingroup$

I wonder why nobody mentioned this:

Horn-Sat vs K-Sat

I guess everybody knows what it is. If not:

Horn-Sat is to find if a set of horn clauses is satisfiable (each clause has at most 1 positive literal).

K-Sat is to find if a set of clauses is satisfiable (each clause can have more than 1 positive literals).

So allowing more than one positive literal in each clause makes the problem from P-complete NP-complete.

$\endgroup$
7
$\begingroup$

Graph Coloring

As mentioned in another answer, 2-COL is solvable in polynomial time while 3-COL is NP-complete. But when increasing the number of colors, after some (unknown?) point the problem gets easier!

For example, if we have N vertices and N colors, the problem can be solved by assigning a different color to each vertex.

$\endgroup$
6
$\begingroup$

In a similar vein: Permanent vs Determinant.

$\endgroup$
  • 3
    $\begingroup$ The difference between perm and det is actually much more significant and of a different kind than the other hardness jumps discussed in the question and the other answers. Negation is very powerful: in a sense it's what allows us to compute det easily but not perm; Valiant has a paper "Negation can be exponentially powerful" portal.acm.org/citation.cfm?id=804412; lots of lower bounds are known for monotone complexity (even in the algebraic model, where monotonicity excludes negations and negative constants), but very few of these translate to non-monotone complexity. $\endgroup$ – Joshua Grochow Nov 1 '10 at 2:27
  • 3
    $\begingroup$ Another example: negation is also necessary for Strassen's algorithm for multiplying 2x2 matrices. Without it you cannot beat the trivial algorithm for multiplying 2x2 matrices. $\endgroup$ – Joshua Grochow Nov 1 '10 at 2:28
6
$\begingroup$

I just read a paper that deals with hypergraph partitioning. The Problem is defined as this, quote:

Given two parameters $k$ and $l$, $1 \leq l < k$, the problem [$P^l_k$] is defined as follows: Let $\mathcal{H} = (V, \mathcal{E})$ be a hypergraph and $t_1, \dots, t_k$ be non-negative integers such that $|V| = n = \sum^k_{i=1} t_i$ and $|\mathcal{E}| = m$. Does there exist a colouring (partition) of $V$ in $k$ subsets of size $t_1, \dots, t_k$ such that the vertices of each hyperedge in $\mathcal{E}$ are coloured with at most $l$ colours?

In general, it is proven that:

  • $P^1_k$ is solvable in polynomial time (in $n,m$) for fixed $k \geq 2$
  • $P^l_k$ is NP-complete for all fixed $2 \leq l < k$

If this is not "jump" enough, read on. For hypergraphs with disjoint hyperedges, it is shown:

  • $P^1_k$ is NP-complete for all fixed $k \geq 2$
  • $P^l_k$ is solvable in linear time (in $m$) for fixed $2 \leq l < k$

Laurent Lyaudet. 2010. NP-hard and linear variants of hypergraph partitioning. Theor. Comput. Sci. 411, 1 (January 2010), 10-21. http://dx.doi.org/10.1016/j.tcs.2009.08.035

$\endgroup$
5
$\begingroup$

Interesting complexity jumps are known for the job shop scheduling problem.

In the job shop problem we have a set of $n$ jobs that must be processed on a given set $M$ of $m$ machines. Each job $j$ consists of a chain of $\mu_j$ operations $O_{1j},O_{2j},\dots,O_{\mu_jj}$. Operation $O_{ij}$ must be processed during $p_{ij}$ time units without interruption on machine $m_{ij}\in M$. A feasible schedule is one in which operation is scheduled only after all its preceding operations have been completed, and each machine processes at most one operation at a time. For any given schedule, let $C_j$ be the completioon time of the last operation of job $j$. Taken here.

There are such objectives as minimizing the makespan $C_{max}=max_jC_j$ and total completion time $\sum C_j$. Regular criteria are defined here.

In the notation of Graham et al. this problem is denoted as $J||\gamma$, where $\gamma$ denotes the objective function to be minimized.

$J2|n=k|F$ and $J|n=2|F$ are polynomially solvable. Here $J2$ $(n=k)$ means that the number of machines (jobs) is fixed and equals $2$ $(k)$. $F$ means an arbitrary regular criterion.

$J3|n=3|C_{max}$, $J3|n=3|\sum C$ are weakly NP-hard.

$J2||C_{max}$, $J2||\sum C$ are strongly NP-hard.

Thus, here we can see that there is a jump when we go from two jobs/machines to three.

$\endgroup$
  • 1
    $\begingroup$ Good, I'm confused with the special terminology. Could you please simplify the terminology (or even better remove it)? $\endgroup$ – Mohammad Al-Turkistany Dec 10 '10 at 8:58
1
$\begingroup$

In many cases, approximating NP-optimization problems give rise to sharp complexity jumps. For example, SET COVER can be approximated within a factor of $\ln n$ in polynomial time (by the Greedy Algorithm), but it is NP-hard to approximate within a factor of $(1-o(1))\ln n$.

$\endgroup$
0
$\begingroup$

I think the pascal triangle would be it. Each row in the pascal triangle sums to $2^n$. The elements are binomial coefficients. So if you find a problem whose performance can be described using binomial coefficients, then simply solving all such problems associated to the n'th row of the pascal triangle already takes $2^n$. But note that $(a+b)^n=\sum_{i\in{0..n}}{{n}\choose{i}}a^ib^{n-i}$ can be represented as a polynomial (of 'a') that has binomial coefficient times powers of 'b' as factors. If 'b' is constant this is a n'th order polynomial $p_b(a)$. Setting $a=b=1$ you get expansion of $2^n=p_1(1)$ as a sum. Now suppose you have a matrix of problems with performance in two variables proportional to binomial coefficients (compared to problem size described by two variables) arranged like a pascal triangle. Then solving all problems in n'th row must take $DTIME(2^n)$. Binomial coefficients describe how many different ways there are to choose k-combinations from n elements. So if your algorithm depends on enumerating k-combinations of n elements $(k<n)$ the algorithm cannot be polynomial time. Because if this problem was polynomial time, then above argument proves $P=NP=DTIME(2^n)$, since sum of two polynomials is a polynomial. But correct proofs of $P=NP$ problem either way are rare.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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