2
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ You can reduce 3col to this. Just set the maximum limit of all colours to $n$ $\endgroup$ – jjohn Nov 10 '15 at 2:27
  • $\begingroup$ I'm not sure if I follow. Sorry if it is that obvious, I just don't see it yet. What if a graph was actually 3COL, but only when all he colors were used $2n$ times? ($n$ needs to be fixed) $\endgroup$ – Jules Nov 10 '15 at 2:51
  • $\begingroup$ cstheory.stackexchange.com/q/33082/6973 ​ ​ $\endgroup$ – user12859 Dec 14 '15 at 22:14
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.