3-COL with a restriction on a number of vertices colored with a particular color

Question

If I modify a 3-COL problem (with colors A, B, C) in a way that I now demand that at most, say, 50 vertices may be colored with color A, does the problem still remain NP-complete?

I've been thinking of a reduction from a standard 3-COL, but there is no way that I can solve a standard 3-colorability using the problem described above; I'd have to cut the graph into smaller pieces. Other NP-complete problems I know of, like independence set, have a parameter and in my problem there is a fixed number instead of a parameter. So this got me thinking, that maybe such a problem could be solved in P-time, but this doesn't make sense as I could probably replace 50 with any other number.

So this is simpler than asking whether there is a 3-COL such that at most k vertices receive color A, but still quite hard in general I think.

Am I correct?

Answer 1

For a fixed parameter like 50, the problem can be solved in "polynomial time": guess which vertices to color A, then solving a 2-coloring problem for the remaining vertices. The running time will be something like $O(|V|^{52})$, since there are $O(|V|^{50})$ ways to choose a set of at most 50 vertices; and 2-coloring can be solved in $O(|V|+|E|)=O(|V|^2)$ time.

Of course, this solution is solely of theoretical interest. An algorithm whose running time is $O(|V|^{52})$ is technically polynomial-time, but it's completely and totally infeasible in practice for any interesting graph.

In contrast, if the parameter 50 is part of the input, then the problem remains NP-hard (consider what happens when you pass in $|V|$ as the value of this input; then you have the standard 3-COL problem). This highlights the difference between a value that is fixed vs is an input to the problem.

Perhaps a simpler example to illustrate that difference is vertex cover: vertex cover is NP-complete, but if I ask you whether there exists a vertex cover of size $\le 50$, that can be done in polynomial time, for similar reasons -- the running time will be $O(|V|^{50})$ or so. In particular, if you want to know whether there exists a vertex cover of size $\le k$, that can be done in $O(|V|^k)$ time. When $k$ is a fixed constant, this is polynomial time; but when $k$ is part of the input, then this is exponential time (it is $\ge 2^k$).

Answer 2

If at most 50 vertices can be colored A, then the problem is in $\mathsf{P}$. Indeed, there are $O(n^{50})$ possibilities for the set of vertices colored A. Go over all such choices in which these vertices are an independent set, delete them, and check whether the remaining graph is bipartite.