63
$\begingroup$

I'm looking for examples of problems parametrized by a number $k \in \mathbb{N}$, where the problem's hardness is non-monotonic in $k$. Most problems (in my experience) have a single phase transition, for example $k$-SAT has a single phase transition from $k \in \{1,2\}$ (where the problem is in P) to $k \ge 3$ (where the problem is NP-complete). I'm interested in problems where there are phase transitions in both directions (from easy to hard and vice-versa) as $k$ increases.

My question is somewhat similar to the one asked at Hardness Jumps in Computational Complexity, and in fact some of the responses there are relevant to my question.

Examples I am aware of:

  1. $k$-colorability of planar graphs: In P except when $k=3$, where it is NP-complete.
  2. Steiner tree with $k$ terminals: In P when $k=2$ (collapses to shortest $s$-$t$ path) and when $k=n$ (collapses to MST), but NP-hard "in between". I don't know if these phase transitions are sharp (e.g., P for $k_0$ but NP-hard for $k_0+1$). Also the transitions of $k$ depend on the size of input instance, unlike my other examples.
  3. Counting satisfying assignments of a planar formula modulo $n$: In P when $n$ is a Mersenne prime number $n=2^k-1$, and #P-complete for most(?)/all other values of $n$ (from Aaron Sterling in this thread). Lots of phase transitions!
  4. Induced subgraph detection: The problem is not parametrized by an integer but a graph. There exist graphs $H_1 \subseteq H_2 \subseteq H_3$ (where $\subseteq$ denotes a certain kind of subgraph relation), for which determining whether $H_i \subseteq G$ for a given graph $G$ is in P for $i\in \{1,3\}$ but NP-complete for $i=2$. (from Hsien-Chih Chang in the same thread).
Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ Minor correction re example (3): the problem is in $\mathsf{P}$ if $n$ is a Mersenne-type integer, i.e., $n=2^k-1$ for some natural number $k$; $n$ does not have to be a prime. (For example, $2^{11}-1$ is not prime.) Unless $n$ is of this form, the problem is #$\mathsf{P}$-complete. $\endgroup$
    – Aaron Sterling
    Commented Dec 2, 2010 at 21:21
  • $\begingroup$ Thanks @Aaron Sterling -- I have revised that example appropriately. $\endgroup$
    – mikero
    Commented Dec 2, 2010 at 22:05
  • 1
    $\begingroup$ Major correction re example (3): The formulas also need to be monotone, read-twice, and have size $k$ clauses, where $n = 2^k - 1$, to be tractable. This was proved by Jin-Yi Cai and Pinyan Lu. This is not how Valiant motivated it. He fixed the clause size to 3 and then varied just the modulus. It was known to be hard in characteristic 0. Valiant showed hardness mod 2 and tractability mod 7. The hardness mod 2 is $\otimes P = \#_2 P$ hardness, not #P-hardness. I don't know what parameterized family of problems you are trying to describe. $\endgroup$
    – Tyson Williams
    Commented Dec 13, 2013 at 4:37
  • 1
    $\begingroup$ For more on this, including the paper references, see Holographic_algorithm#History on Wikipedia. $\endgroup$
    – Tyson Williams
    Commented Dec 13, 2013 at 4:41
  • $\begingroup$ Is there a standard term for this transition from P to NPC or vice versa? Unfortunately, the term `phase transition' is taken, i.e. used in a different meaning (link). $\endgroup$
    – Cyriac Antony
    Commented Sep 7, 2021 at 16:22

12 Answers 12

Reset to default
27
$\begingroup$

One field with lots of non-monotonicity of problem complexity is property testing. Let $\mathcal{G}_n$ be the set of all $n$-vertex graphs, and call $P \subseteq \mathcal{G}_n$ a graph property. A generic problem is to determine whether a graph $G$ has property $P$ (i.e. $G \in P$) or is `far' from having property $P$ in some sense. Depending on what $P$ is, and what kind of query access you have to the graph, the problem can be quite difficult.

But it is easy to see that the problem is non-monotone, in that if we have $S \subset P \subset T$, the fact that $P$ is easily testable does not imply either that $S$ is easily testable or that $T$ is.

To see this, it is enough to observe that $P = \mathcal{G}_n$ and $P = \emptyset$ are both trivially testable, but that for some properties, there exist strong lower bounds.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Could you please mention (or point to) a non-trivial example? I guess you know some already. It is also interesting whether there are P $\to$ NP $\to$ P $\to$ NP phase transitions. $\endgroup$
    – Cyriac Antony
    Commented Jan 25, 2019 at 6:20
23
$\begingroup$

For a given graph $G$ and an integer $k\ge 1$, the $k$-th power of $G$, denoted by $G^k$, has the same vertex set such that two distinct vertices are adjacent in $G^k$ if their distance in $G$ is at most $k$. The $k$-th power of split graph problem asks if a given graph is the $k$-th power of a split graph.

Improve this answer
$\endgroup$
18
$\begingroup$

One of such problems is edge coloring of planar graphs where the parameter is $\Delta$ - maximal degree of a graph. When $\Delta=2$ or $\Delta\geqslant 7$ there are known polynomial exact algorithms for it (see here), whereas for $3\leqslant\Delta\leqslant 6$ such algorithms are not known and there are no NP-hardness proofs for these cases.

The related question is discussed here.

Improve this answer
$\endgroup$
15
$\begingroup$

Determining whether a graph $G$ has a dominating clique for:

  • $diam(G)=1$ is trivial -- answer is always 'yes'
  • $diam(G)=2$ is NP-complete
  • $diam(G)=3$ is NP-complete
  • $diam(G)\ge 4$ is trivial -- answer is always 'no'

The case $diam(G)=3$ is due to Brandstädt and Kratsch, and the case $diam(G)=2$ is noted in a recent paper of mine.

Improve this answer
$\endgroup$
2
13
$\begingroup$

Is this is an example of the phenomenon you're looking for?

Consider the k-Clique problem, where k is the size of the clique we're searching for. So the problem is "Is there a clique of size k in the graph G on n vertices?"

For all constants k, the problem is in P. (The brute force algorithm runs in time $O(n^k)$.) For large values of k, for example values like n/2, it is NP-complete. When k gets very close to n, like n-c for some constant c, the problem is in P again because we can search over all subsets of n vertices of size n-c and check if any of them forms a clique. (There are only $O(n^c)$ such subsets, which is polynomially large when c is a constant.)

Improve this answer
$\endgroup$
5
  • 7
    $\begingroup$ This phenomenon is only because we might as well view k as min(k, n-k), and either solve k-clique or k-indept set (really the same problem). If we think of 0 < k <= n/2 for this reason, the complexity is strictly increasing in k. $\endgroup$
    – Aaron Roth
    Commented Dec 2, 2010 at 19:40
  • 5
    $\begingroup$ @Aaron: I am afraid that your argument is not correct. Finding a clique of size n−k is very different from finding an independent set of size k. You must be confused by the fact that finding a clique of size k in a graph G is equivalent to finding an independent set of size k in the complement of G. $\endgroup$
    – Tsuyoshi Ito
    Commented Dec 2, 2010 at 20:23
  • $\begingroup$ Tsuyoshi: Yes, of course. I intended to say that WLOG, you can assume k <= n/2, since if not, take the complement graph and solve the problem for k' = n-k. And of course, this highlights that the complexity is increasing in k. $\endgroup$
    – Aaron Roth
    Commented Dec 2, 2010 at 20:34
  • 2
    $\begingroup$ @Aaron: “if not, take the complement graph and solve the problem for k' = n-k.” That is exactly the incorrect claim I am trying to object. Let me repeat what I said: “finding a clique of size k in a graph G is equivalent to finding an independent set of size k in the complement of G.” Finding a clique of size k in a graph G is not equivalent to finding a clique of size n−k in the complement of G. $\endgroup$
    – Tsuyoshi Ito
    Commented Dec 2, 2010 at 21:23
  • 2
    $\begingroup$ Ah, yes. :-) That was silly, I retract my objection. What is going on here is only that Binomial[n,k] = Binomial[n,n-k], and so the running time of exhaustive search is monotone increasing for k < n/2, and monotone decreasing for k > n/2. $\endgroup$
    – Aaron Roth
    Commented Dec 2, 2010 at 22:09
12
$\begingroup$

Here's an example that might be of the type you're looking for. The parameter is not an integer though, it's a pair of numbers. (Although one of them can be fixed to make it a one parameter problem.)

The problem is to evaluate the Tutte polynomial of a graph G at coordinates (x,y). We can restrict the coordinates to be integers. The problem is in P if (x,y) is one of the points (1, 1), (-1,-1), (0,-1), (-1,0), or satisfies (x-1)(y-1)=1. Otherwise it is #P-hard.

I got this from Wikipedia's article on the Tutte polynomial.

Improve this answer
$\endgroup$
12
$\begingroup$

What about the question of computing the permanent of a matrix modulo $k$? For $k=2$ this is easy (since permanent=determinant), and Valiant (in "The complexity of computing the permanent") showed it can be computed modulo $2^d$ in time $O(n^{4d-3})$ for $d \geq 2$ by a modified variant of Gaussian elimination. But for $k$ which is not a power of $2$, it is UP-Hard.

Improve this answer
$\endgroup$
11
$\begingroup$

Another problem with this phenomenon is the MINIMUM $t$-SPANNER problem on split graphs.

For a constant $t$, a $t$-spanner of a connected graph $G$ is a connected spanning subgraph $H$ of $G$ such that for every pair of vertices $x$ and $y$, the distance between $x$ and $y$ in $H$ is at most $t$ times their distance in $G$. The MINIMUM $t$-SPANNER problem asks for a $t$-spanner with minimum number of edges of a given graph.

A split graph is a graph whose vertex set can be partitioned into a clique and an independent set.

In this paper it was shown that MINIMUM 2-SPANNER on split graphs is NP-hard while for each $t \ge 3$, MINIMUM $t$-SPANNER is easy on split graphs.

Improve this answer
$\endgroup$
11
$\begingroup$

This is an interesting (and surprising) example for a P $\to$ NP-hard $\to$ P $\to$ NP-hard $\to \cdots$ phase transition:

Deciding if a complete graph on $n$ vertices, in which each vertex has a strict ranking of all other vertices, admits a popular matching is in P for odd $n$ and NP-hard for even $n$. (The parameter is the vertex number $n$.)

The proof has been announced in this paper.

Improve this answer
$\endgroup$
1
  • $\begingroup$ A very interesting one. Consider adding the title of the paper in your answer (just in case the link gets dead in future). $\endgroup$
    – Cyriac Antony
    Commented Jan 28, 2022 at 6:14
10
$\begingroup$

Well known example is $k$-edge coloring.

It is decidable in polynomial time if $k \ne \Delta$ otherwise it is $NP$-complete.

For cubic graphs, deciding the existence of edge coloring using:

  • $k=2$ colors is trivial since the answer is always no.
  • $k=3$ colors is $NP$-complete
  • $k \ge 4$ colors is trivial since answer is always yes.

Holyer, Ian (1981), "The NP-completeness of edge-coloring", SIAM Journal on Computing 10: 718–720

http://en.wikipedia.org/wiki/Edge_coloring

Improve this answer
$\endgroup$
1
  • $\begingroup$ Could you, please, add a reference? $\endgroup$
    – Oleksandr Bondarenko
    Commented Feb 27, 2011 at 18:31
8
$\begingroup$

A path in an edge-colored graph is rainbow if no color appears twice on it. A graph is rainbow colored if there is a rainbow path between each pair of vertices. Let RAINBOW-$k$-COLORABILITY be the problem of deciding if a given graph can be rainbow colored using $k$ colors.

For any graph $G$, the problem is easy for $k=1$ as it equals checking if $G$ is a complete graph. For split graphs, the problem is $\sf NP$-complete for $k \in \{2,3\}$, and in $\sf P$ for all other values of $k$.

See Chandran, L. Sunil, Deepak Rajendraprasad, and Marek Tesař. "Rainbow Colouring of Split Graphs." arXiv preprint arXiv:1404.4478 (2014).

Improve this answer
$\endgroup$
8
$\begingroup$

A subset $U\subseteq V(G)$ of a graph $G$ is a disconnected cutset if $G[U]$ and $G-U$ are disconnected.

Deciding if a graph of diameter 1 has a disconnected cutset is trivial. The problem becomes NP-hard on graphs of diameter 2 see this paper and is again easy on graphs of diameter at least 3 see this paper.

Improve this answer
$\endgroup$

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.