Parameterized complexity from P to NP-hard and back again

Question

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

Answer 1

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.

Answer 2

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.

• For $k=1$, the problem solvable in linear time. This is because recognizing split graphs is doable in linear time (well known).
• For $k=2$, the problem is NP-complete. This is proved by Lau and Corneil in Recognizing powers of proper interval, split, and chordal graph, SIAM J. Discrete Math., 18 (2004), 83-102.
• For $k\ge 3$, the problem is trivial: only complete graphs are $k$-th powers of a split graph.

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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

Answer 11

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

Answer 12

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.