<p>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 <a href="http://www.graphclasses.org/classes/gc_39.html">split graph</a> 
problem asks if a given graph is the $k$-th power of a split graph. </p>

<ul>
<li>For $k=1$, the problem solvable in linear time. This is because recognizing split graphs 
is doable in linear time (well known).</li>
<li>For $k=2$, the problem is NP-complete. This is proved by <a href="http://epubs.siam.org/doi/abs/10.1137/S0895480103425930">Lau and Corneil in <em>Recognizing powers 
of proper interval, split, and chordal graph</em>, SIAM J. Discrete Math., 18 (2004), 83-102</a>.</li>
<li>For $k\ge 3$, the problem is trivial: only complete graphs are $k$-th powers of a split graph.</li>
</ul>

CC BY-SA 3.0
2013-04-29T15:22:02.057Z
2013-04-29T15:22:02.057Z
vb le
<p>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 (<a href="http://dx.doi.org/10.1007/s00453-007-9044-3" rel="nofollow noreferrer">see here</a>), whereas for $3\leqslant\Delta\leqslant 6$ such algorithms are not known and there are no NP-hardness proofs for these cases.</p>

<p>The related question is discussed <a href="https://cstheory.stackexchange.com/questions/2578/complexity-of-edge-coloring-in-planar-graphs">here</a>.</p>

CC BY-SA 2.5
2010-12-02T23:47:08.927Z
2010-12-03T00:14:20.130Z
2017-04-13T12:32:28.167Z
Oleksandr Bondarenko
<p>Is this is an example of the phenomenon you're looking for?</p>

<p>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?" </p>

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

CC BY-SA 2.5
2010-12-02T19:40:12.510Z
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
CC BY-SA 2.5
2010-12-02T20:23:32.723Z
@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
CC BY-SA 2.5
2010-12-02T20:34:59.423Z
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
CC BY-SA 2.5
2010-12-02T21:23:15.690Z
@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
CC BY-SA 2.5
2010-12-02T22:09:55.043Z
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
CC BY-SA 2.5
2010-12-02T19:30:25.310Z
2010-12-02T19:30:25.310Z
Robin Kothari
<p>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.)</p>

<p>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. </p>

<p>I got this from <a href="http://en.wikipedia.org/wiki/Tutte_polynomial">Wikipedia's article on the Tutte polynomial</a>.</p>

CC BY-SA 2.5
2010-12-03T04:52:58.797Z
2010-12-03T04:52:58.797Z
Robin Kothari
<p>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 "<a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6V1G-45FCXDC-5Y&amp;_user=10&amp;_coverDate=12%2F31%2F1979&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_origin=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1566271121&amp;_rerunOrigin=scholar.google&amp;_acct=C000050221&amp;_version=1&amp;_urlVersion=0&amp;_userid=10&amp;md5=9d1567e9b1ce681a065a8df5dae36365&amp;searchtype=a">The complexity of computing the permanent</a>") 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.  </p>

CC BY-SA 2.5
2010-12-03T18:08:48.507Z
2010-12-03T18:08:48.507Z
Kevin Costello
<p>This is an interesting (and surprising) example for a P <span class="math-container">$\to$</span> NP-hard <span class="math-container">$\to$</span> P <span class="math-container">$\to$</span> NP-hard <span class="math-container">$\to \cdots$</span> phase transition: </p>

<p>Deciding if a complete graph on <span class="math-container">$n$</span> vertices, in which each  vertex has a strict ranking of all other vertices, admits a popular matching is in P for odd <span class="math-container">$n$</span> and NP-hard for even <span class="math-container">$n$</span>. (The parameter is the vertex number <span class="math-container">$n$</span>.) </p>

<p>The proof has been announced in <a href="http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=9916" rel="noreferrer">this paper</a>.</p>

CC BY-SA 4.0
2022-01-28T06:14:56.237Z
A very interesting one. Consider adding the title of the paper in your answer (just in case the link gets dead in future).
Cyriac Antony
CC BY-SA 4.0
2019-07-20T19:45:41.953Z
2019-07-20T19:45:41.953Z
user13136
<p>Another problem with this phenomenon is the MINIMUM $t$-SPANNER problem on split graphs. </p>

<p>For a constant $t$, a <em>$t$-spanner</em>  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. </p>

<p>A <em>split graph</em> is a graph whose vertex set can be partitioned into a clique and an independent set. </p>

<p>In <a href="http://www.sciencedirect.com/science/article/pii/S0890540197926419">this paper</a> 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.</p>

CC BY-SA 3.0
2013-04-21T13:37:46.113Z
2013-04-22T09:09:44.357Z
2013-04-22T09:09:44.357Z
user13136
<p>Determining whether a graph $G$ has a dominating clique for:</p>

<ul>
<li>$diam(G)=1$ is trivial -- answer is always 'yes'</li>
<li>$diam(G)=2$ is NP-complete</li>
<li>$diam(G)=3$ is NP-complete </li>
<li>$diam(G)\ge 4$ is trivial -- answer is always 'no'</li>
</ul>

<p>The case $diam(G)=3$ is due to <a href="http://www.sciencedirect.com/science/article/pii/0304397587901289">Brandstädt and Kratsch</a>, and the case $diam(G)=2$ is noted in <a href="http://www.sciencedirect.com/science/article/pii/S0377221713009533">a recent paper of mine</a>.</p>

CC BY-SA 3.0
2013-12-29T12:52:15.057Z
+1 Nice answer. What is dominating clique?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-12-29T14:50:56.123Z
Just like it sounds -- a [dominating set](http://en.wikipedia.org/wiki/Dominating_set) that is also a [clique](http://en.wikipedia.org/wiki/Clique_%28graph_theory%29).
Austin Buchanan
CC BY-SA 3.0
2013-12-06T02:09:13.550Z
2013-12-29T04:28:56.580Z
2013-12-29T04:28:56.580Z
Austin Buchanan
<p>A subset $U\subseteq V(G)$ of a graph $G$ is a <em>disconnected cutset</em> if $G[U]$ and $G-U$ are disconnected.</p>

<p>Deciding if a graph of diameter 1 has a disconnected cutset is trivial.
The problem becomes NP-hard on graphs of diameter 2
<a href="http://link.springer.com/chapter/10.1007%2F978-3-642-23786-7_43">see this paper</a>
and is again easy on graphs of diameter at least 3 <a href="http://www.sciencedirect.com/science/article/pii/S0304397508009407">see this paper</a>.</p>

CC BY-SA 3.0
2015-08-01T17:05:07.503Z
2015-08-01T17:05:07.503Z
user13136
<p>A path in an edge-colored graph is <em>rainbow</em> if no color appears twice on it. A graph is <em>rainbow colored</em> 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.</p>

<p>For any graph $G$, the problem is easy for $k=1$ as it equals checking if $G$ is a complete graph. For <a href="http://en.wikipedia.org/wiki/Split_graph">split graphs</a>, the problem is $\sf NP$-complete for $k \in \{2,3\}$, and in $\sf P$ for all other values of $k$.</p>

<p>See <a href="http://arxiv.org/pdf/1404.4478v1.pdf">Chandran, L. Sunil, Deepak Rajendraprasad, and Marek Tesař. "Rainbow Colouring of Split Graphs." arXiv preprint arXiv:1404.4478 (2014).</a></p>

CC BY-SA 3.0
2014-04-25T10:36:09.720Z
2014-04-25T10:36:09.720Z
Juho
<p>Well known example is $k$-edge coloring.</p>

<p>It is decidable in polynomial time if $k \ne \Delta$ otherwise it is <a href="http://epubs.siam.org/sicomp/resource/1/smjcat/v10/i4/p718_s1?isAuthorized=no">$NP$-complete</a>. </p>

<p>For cubic graphs, deciding the existence of edge coloring using:</p>

<ul>
<li>$k=2$ colors is trivial since the answer is always no.</li>
<li>$k=3$ colors is $NP$-complete</li>
<li>$k \ge 4$ colors is trivial since answer is always yes.</li>
</ul>

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

<p><a href="http://en.wikipedia.org/wiki/Edge_coloring">http://en.wikipedia.org/wiki/Edge_coloring</a></p>

CC BY-SA 2.5
2011-02-27T18:31:03.293Z
Could you, please, add a reference?
Oleksandr Bondarenko
CC BY-SA 3.0
2011-02-27T18:17:32.660Z
2013-12-06T05:56:25.800Z
2013-12-06T05:56:25.800Z
Mohammad Al-Turkistany
<p>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.</p>

<p>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.  </p>

<p>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.</p>

CC BY-SA 4.0
2019-01-25T06:20:16.320Z
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
CC BY-SA 2.5
2010-12-02T20:39:29.733Z
2010-12-02T20:39:29.733Z
Aaron Roth
<p>I'm looking for examples of problems parametrized by a number $k \in \mathbb{N}$, where the problem's hardness is <i>non-monotonic</i> 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 <i>in both directions</i> (from easy to hard and vice-versa) as $k$ increases.</p>

<p>My question is somewhat similar to the one asked at <a href="https://cstheory.stackexchange.com/questions/2447/hardness-jumps-in-computational-complexity">Hardness Jumps in Computational Complexity</a>, and in fact some of the responses there are relevant to my question.</p>

<p>Examples I am aware of:</p>

<ol>
<li>$k$-colorability of planar graphs: In P except when $k=3$, where it is NP-complete.</li>
<li>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.</li>
<li>Counting satisfying assignments of a planar formula modulo $n$: In P when $n$ is a Mersenne <strike>prime</strike> number $n=2^k-1$, and #P-complete for <strike>most(?)/</strike>all other values of $n$ (from Aaron Sterling in <a href="https://cstheory.stackexchange.com/questions/2447/hardness-jumps-in-computational-complexity">this thread</a>). Lots of phase transitions!</li>
<li>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 <a href="https://cstheory.stackexchange.com/questions/2447/hardness-jumps-in-computational-complexity">the same thread</a>).</li>
</ol>

CC BY-SA 3.0
2013-12-13T04:37:55.767Z
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
CC BY-SA 3.0
2013-12-13T04:41:55.053Z
For more on this, including the paper references, see [Holographic_algorithm#History](https://en.wikipedia.org/wiki/Holographic_algorithm#History) on Wikipedia.
Tyson Williams
CC BY-SA 4.0
2021-09-07T16:22:36.930Z
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](https://cstheory.stackexchange.com/a/2680/47855)).
Cyriac Antony
CC BY-SA 4.0
2022-07-19T09:44:47.720Z
@mikero, May I know your full name? (to cite).
Cyriac Antony
CC BY-SA 2.5
2010-12-02T21:21:14.020Z
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
CC BY-SA 2.5
2010-12-02T22:05:16.667Z
Thanks @Aaron Sterling -- I have revised that example appropriately.
mikero
<cc.complexity-theory><np-hardness><big-list><phase-transition>
Parameterized complexity from P to NP-hard and back again
mikero
# Parameterized complexity from P to NP-hard and back again

(Asked by: username_0 on 2010-12-02)

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](https://cstheory.stackexchange.com/questions/2447/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 username_3 in [this thread](https://cstheory.stackexchange.com/questions/2447/hardness-jumps-in-computational-complexity)). 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](https://cstheory.stackexchange.com/questions/2447/hardness-jumps-in-computational-complexity)).

**Tags:** cc.complexity-theory, np-hardness, big-list, phase-transition

> **Comments:**
> **username_3**: 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.  
> **username_0**: Thanks @username_3 -- I have revised that example appropriately.  
> **username_1**: 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.  
> **username_1**: For more on this, including the paper references, see [Holographic_algorithm#History](https://en.wikipedia.org/wiki/Holographic_algorithm#History) on Wikipedia.  
> **username_2**: 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](https://cstheory.stackexchange.com/a/2680/47855)).  
> **username_2**: @username_0, May I know your full name? (to cite).  

---

## 12 answers

### Answer by username_7 on 2010-12-02. Score: 27 | Accepted answer

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.

> **Comments:**
> **username_2**: 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.  

---

### Answer by username_4 on 2013-04-29. Score: 23

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](http://www.graphclasses.org/classes/gc_39.html)
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](http://epubs.siam.org/doi/abs/10.1137/S0895480103425930).
* For $k\ge 3$, the problem is trivial: only complete graphs are $k$-th powers of a split graph.


---

### Answer by username_5 on 2010-12-02. Score: 18

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](http://dx.doi.org/10.1007/s00453-007-9044-3)), 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](https://cstheory.stackexchange.com/questions/2578/complexity-of-edge-coloring-in-planar-graphs).


---

### Answer by username_11 on 2013-12-06. Score: 15

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](http://www.sciencedirect.com/science/article/pii/0304397587901289), and the case $diam(G)=2$ is noted in [a recent paper of mine](http://www.sciencedirect.com/science/article/pii/S0377221713009533).

> **Comments:**
> **username_12**: +1 Nice answer. What is dominating clique?  
> **username_11**: Just like it sounds -- a [dominating set](http://en.wikipedia.org/wiki/Dominating_set) that is also a [clique](http://en.wikipedia.org/wiki/Clique_%28graph_theory%29).  

---

### Answer by username_6 on 2010-12-02. Score: 13

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

> **Comments:**
> **username_7**: 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.  
> **username_8**: @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.  
> **username_7**: 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.  
> **username_8**: @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.  
> **username_7**: 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.  

---

### Answer by username_6 on 2010-12-03. Score: 12

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](http://en.wikipedia.org/wiki/Tutte_polynomial).


---

### Answer by username_9 on 2010-12-03. Score: 12

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](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-45FCXDC-5Y&_user=10&_coverDate=12%2F31%2F1979&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1566271121&_rerunOrigin=scholar.google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=9d1567e9b1ce681a065a8df5dae36365&searchtype=a)") 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 by username_10 on 2019-07-20. Score: 11

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](http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=9916).

> **Comments:**
> **username_2**: A very interesting one. Consider adding the title of the paper in your answer (just in case the link gets dead in future).  

---

### Answer by username_10 on 2013-04-21. Score: 11

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](http://www.sciencedirect.com/science/article/pii/S0890540197926419) 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 by username_12 on 2011-02-27. Score: 10

Well known example is $k$-edge coloring.

It is decidable in polynomial time if $k \ne \Delta$ otherwise it is [$NP$-complete](http://epubs.siam.org/sicomp/resource/1/smjcat/v10/i4/p718_s1?isAuthorized=no).

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>

> **Comments:**
> **username_5**: Could you, please, add a reference?  

---

### Answer by username_10 on 2015-08-01. Score: 8

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](http://link.springer.com/chapter/10.1007%2F978-3-642-23786-7_43)
and is again easy on graphs of diameter at least 3 [see this paper](http://www.sciencedirect.com/science/article/pii/S0304397508009407).


---

### Answer by username_13 on 2014-04-25. Score: 8

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](http://en.wikipedia.org/wiki/Split_graph), 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).](http://arxiv.org/pdf/1404.4478v1.pdf)


---

