13
$\begingroup$
  • 2-SAT is in P; 3-SAT is NP-complete.
  • Exact cover by 2-sets is in P; exact cover by 3-sets is NP-complete
  • Two-dimensional matching is in P; three-dimensional matching is NP-complete
  • Graph 2-coloring is trivially in P; graph 3-coloring is NP-complete

Are there other well-known or important examples that are similar, in that there is a family of problems with a natural parameter $n$, where the problem is known to be in P when $n<3$ and known to be NP-hard when $n≥3$?

$\endgroup$
  • $\begingroup$ There's a lot of "natural" problems like this. What would you consider "important" or "well-known" more precisely? $\endgroup$ – Juho Nov 15 at 22:43
  • $\begingroup$ I don't know. But is it unclear why I might consider the four problems I cited as either important or well-known? $\endgroup$ – Mark Dominus Nov 15 at 22:53
5
$\begingroup$

In graph coloring you are looking for a partitioning of the vertex set into independent sets. Now, there are many arguably well-known similarly behaving (i.e., easy for $k=2$, hard for $k \geq 3$) problems where instead you want to find a partition into $k$ sets which could be (i) independent dominating, (ii) dominating, (iii) total nearly perfect, (iv) weakly perfect dominating, or (v) total perfect dominating, to name a few. Many of these problems also appear under different shorter names like "domatic number", "total domatic number", and so on. For more details, see e.g., the work of Heggernes and Telle [1, Table 1] (there's quite a bit of follow-up work as well).

Also, graph coloring is naturally linked to the classical and heavily-studied chromatic index (i.e., edge coloring) via the line graph. Further, deciding if a $k$-regular graph can be edge $k$-colored properly is NPC for every $k \geq 3$.


[1] Heggernes, Pinar, and Jan Arne Telle. "Partitioning graphs into generalized dominating sets." Nord. J. Comput. 5.2 (1998): 128-142.

$\endgroup$
4
$\begingroup$

There are many problems like this listed in Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael Garey and David S. Johnson. For instance,

  • [ND14] Graph Partitioning: NP-hard for $K\geq3$ and in P for $K=2$.

  • [SP3] Set Packing: NP- hard even for all $c\in C$ with $|c|\leq 3$ but in P if for all $c\in C$ have $|c|\leq 2$.

  • [SP4] Set Splitting and [SP5] Minimum Cover: same constraints as in [SP3].

You can see the cited textbook for a much longer list of problems.

$\endgroup$
4
$\begingroup$

One more example is $k$-partitioning problem, where given a set $A$ of $n$ numbers where $n$ is a multiple of $k$, the goal is to find a partition of $A$ into $k$-tuples, such that the numbers in each tuple sum up to zero.

More specifically, given a set $A$ of $m \cdot k$ elements. The goal is to partition $A$ into $m$ tuples $(a_{i1}, \dots a_{ik})$ for $i \in [m]$ each of size $k$, such that the sum of the numbers in each tuple $a_{i1} + a_{i2} \dots + a_{ik}$ is equal to zero.

The problem is hard for $k \geq 3$. However, for $k = 2$ the problem turns to find if for each value $x \in A$, whether $-x$ is also in $A$ which is doable in linear/almost-linear time. You can also define the problem on multisets and hence the positive-instance condition in case of $k = 2$ turns into $\#_A(x) = \#_A(-x)$ for all $x \in A$.

Note This problem differs from the set partitioning problem, where we are given a set $A$ and the goal is to find a partition of $A$ into $A_1$ and $A_2$ such that $\sum_{x \in A_1} x = \sum_{y \in A_2}y.$

The set partitioning problem admits a psudo-polynomial algorithm and hence is weakly NP-hard meanwhile $k$-partitioning for $k \geq 3$ is a strongly NP-hard problem. Assuming $P \neq NP$, strongly NP-hard problem are strictly harder than weakly NP-hard problem. (For instance, a pseudo polynomial algorithm for the 3-partitioning problem implies a polynomial time algorithm for the 3d-Matching problem which is an NP-hard problem).

Side note. The parameter $n$ is usually used to represent the size of the input. In Graphs it is used as the number of vertices and in sets as the number of elements. Try to avoid using $n$ to name other parameters since that might create confusion. Usually $k$ and $r$ are used for other parameters. Quite often in parameterized complexity $k$ is used as the parameter representing the size of the output (In the running time of output sensitive algorithms). For example, the independence number in the maximum independent set problem and the minimum feedback vertex number in the feedback vertex set problem.

$\endgroup$
2
$\begingroup$

Let $d_1,\ldots,d_n\geq 2$ be positive integers and let $T \in \Bbb R^{d_1\times \ldots \times d_n}$ be a tensor (hypermatrix) of order $n$.


SVD: The singular value decomposition (understood as canonical polyadic decomposition for $n\geq 3$) is NP-hard for $n\geq 3$ (see [1]). Similarly computing the rank of $T$ over any finite field is NP-complete, and it is NP-hard over the reals.


The spectral norm of $T$ is the quantity: $$\|T\| = \sup_{x_1\in\Bbb R^{d_1}\setminus\{0\},\ldots,x_n\in\Bbb R^{d_n}\setminus\{0\}} \frac{\sum_{j_1=1}^{d_1}\cdots \sum_{j_n=1}^{d_n}T_{j_1,\ldots,j_n}x_{1,j_1}\cdots x_{n,j_n}}{\|x_1\|_2\cdots\|x_n\|_{2}}$$ If $n=2$, then this is just the spectral norm of the matrix $T$ whose computation is well-known and can be done in polynomial time (just do an SVD of $T$ and $\|T\|$ is the maximal singular value). However, if $n\geq 3$, then the problem is NP-hard (see [1]). Actually, in the mentioned reference, you will find plenty of problems whith the same flavor (NP-hard for tensors of order $n\geq 3$ and "easy" for matrices $n=2$).

[1] Tensor rank is NP-complete, Johan Håstad, J. of Algorithms 11.4 (1990), https://link.springer.com/chapter/10.1007/BFb0035776

[2] Most Tensor Problems Are NP-Hard, Hillar, Christopher J. and Lim, Lek-Heng, J. ACM (2013), https://dl.acm.org/citation.cfm?id=2512329

$\endgroup$
1
$\begingroup$

Can you color a planar graph with k colours?

k = 0, k = 1: Trivial.

k = 2: Easy peasy.

k = 3: NP-complete.

k = 4: Very, very hard proof that the answer is always "Yes".

k = 5, 6, 7, etc. : Easy proof that the answer is always "Yes".

$\endgroup$
  • $\begingroup$ From an algorithmic complexity point of view $k \geq 4$ is also trivial :) $\endgroup$ – orlp Nov 18 at 12:39
  • $\begingroup$ For k=0,1 you still have to look at the graph. K>=4 is easier, you don’t even need to look at the graph. That’s more than trivial:-) $\endgroup$ – gnasher729 Nov 18 at 15:45

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.