# Parameterized complexity from P to NP-hard and back again

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).
• 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. – Aaron Sterling Dec 2 '10 at 21:21
• Thanks @Aaron Sterling -- I have revised that example appropriately. – mikero Dec 2 '10 at 22:05
• 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. – Tyson Williams Dec 13 '13 at 4:37
• For more on this, including the paper references, see Holographic_algorithm#History on Wikipedia. – Tyson Williams Dec 13 '13 at 4:41
• A concern regarding example (4): I hope you mean that $H \subseteq G$ denote $G$ being a realization of the $s$-graph $H$. But how can we say that theta $\subseteq$ prism $\subseteq$ pyramid? Note that we are talking about induced subgraphs not subgraphs. – Cyriac Antony Jan 25 at 5:42

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.

• 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. – Cyriac Antony Jan 25 at 6:20

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.

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.

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.

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

• 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. – Aaron Roth Dec 2 '10 at 19:40
• @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. – Tsuyoshi Ito Dec 2 '10 at 20:23
• 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. – Aaron Roth Dec 2 '10 at 20:34
• @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. – Tsuyoshi Ito Dec 2 '10 at 21:23
• 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. – Aaron Roth Dec 2 '10 at 22:09

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.

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.

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.

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

• Could you, please, add a reference? – Oleksandr Bondarenko Feb 27 '11 at 18:31

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.

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

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.