Assuming P = NP, how would one solve the graph coloring problem in polynomial time?

Question

Assuming we have $\sf P = NP$, how would I show how to solve the graph coloring problem in polynomial time?

Given a graph $G = (V,E)$, find a valid coloring $\chi(G) : V \to \{1,2,\cdots,k\}$ for some $k$ satisfying the property that $(u,v) \in E$ implies $\chi(u)\ne\chi(v)$ so as to minimize the fewest number $k$ of “colors”.

Answer 1

There are two cases:

1. $P = NP$ non-constructively: this means we have derived a contradiction from the assumption that $P \neq NP$, and thus can conclude that $P = NP$ by the law of the excluded middle. In this case, we have no idea what an algorithm to solve graph coloring in polynomial time looks like, or any other problem. We know one exists, because we know that if it doesn't exist, we can derive a contradiction. So a proof of this form is pretty useless for solving problems quickly.

2. $P = NP$ constructively. In this case, we have a polynomial time algorithm for some $NP$-hard problem, let's say $L$. If $L$ is NP-hard, then it must solve some other NP-hard problem in polynomial time (i.e. it reduces from that problem). That problem, in turn, either reduces from another problem, or has a direct reduction from every problem in $NP$. We keep following the trail of reductions until we get to one with a direct proof (probably 3SAT).

   By composing these reductions, we get an algorithm that solves 3SAT in polynomial time (because each reduction only makes a polynomial number of calls to the previous algorithm, and our starting algorithm for $L$ runs in polynomial time.

   We then plug that algorithm into the reduction from Cook-Levin theorem, which gives us a way to simulate any algorithm running in Polynomial time with a polynomial number of calls to a 3SAT solver. Again, a polynomial number of calls to a polynomial-time algorithm runs in polynomial time.

   Finally, there is a simple non-deterministic algorithm that solves Graph-coloring in polynomial time: just guess a coloring and check if it's valid. So we use Cook-Levin to simulate this algorithm in polynomial time.

   As you can imagine, each time we have to compose a reduction, the degree of our polynomial is going to get higher and higher. So it's entirely possible that $P = NP$ but graph colouring can only be solved in, say, $O(n^{100000000000000})$ time. This is still polynomial time, but it really doesn't buy us much in terms of practically solving problems.

Answer 2

If P=NP, that means there is for any given problem in NP, for example, the problem "Is $G$ $k$-colourable?", where $G$ is a finite graph and $k$ an integer, there is an algorithm to solve it in polynomial time.

Unfortunately, our problem is not in NP. We want to find a $k$-colouring for the minimum possible $k$. Now we can find the minimum possible $k$ in polynomial time just by repeatedly solving the problem above for $k=1,2,\ldots$, until it returns the answer "yes". (Note this happens by the time $k$ reaches the number of vertices, if not earlier, so only a polynomial number of instances are needed.)

But now that we know $k$, how do we find a $k$-colouring? Well, if $k$ equals the number of vertices, that's easy: every vertex must have a different colour. If $k$ is less than the number of vertices, then in any colouring (and we know one exists), there are two vertices $x$ and $y$ of the same colour (which must be non-adjacent). That means that we can combine $x$ and $y$ (remove them and replace them with a new vertex which is adjacent to every neighbour of $x$ or $y$), and the same colouring works for this new graph. So this new graph is also $k$-colourable, and has one fewer vertex.

So what we can do is run over all pairs of non-adjacent vertices $x,y$ and check whether the new graph formed by combining $x$ and $y$ is $k$-colourable, until we get an answer "yes" (this must eventually happen). We then repeat this process, keeping track of which original vertices were combined to form each current vertex, until the graph only has $k$ vertices. This divides the vertices of the original graph into $k$ sets, and we can just give each set its own colour to obtain a $k$-colouring of $G$.

Answer 3

The following roughly sketched algorithm, assuming P=NP, finds a 3 coloring of the input graph if one exists, in polynomial time. If there's no such 3 coloring, though, it never terminates.

First, learn to enumerate all possible algorithms (Turing machines), and to simulate computation of any such Turing machine on arbitrary input.

Second, learn to enumerate all possible algorithms with an attached poly-time alarm clock. (That means that we will be enumerating a special case of Turing machines that conceptually do two things in parallel; on one set of tapes, they compute the "primary problem", and on a separate tape they just count down to zero from a fixed one of functions n, 2*n^2, 3*n^3, ..., where n is the length of the input to the primary problem, halting the computation (perhaps prematurely from the perspective of the primary problem) once this countdown on the separate tape (called alarm clock) reaches zero before the primary problem is solved. So sometimes the computation is terminated because an output has been provided for the primary problem, and sometimes the computation is terminated by the alarm clock, with the output tape containing whatever it happens to.)

The exact order in which the Turing machines with an attached polynomial alarm clock are enumerated should be exhaustive: it should be such that we'll encounter every combination of a Turing machine and of an alarm clock function among the ones suggested above sooner or later.

Now, learn to simulate all these Turing machines with an attached polynomial alarm clock in parallel, starting them well spaced in time one by one. In particular, make sure that almost one half of the total running time is devoted to the first Turing machine with an attached polynomial alarm clock in the enumeration, almost one quarter of total running time to the second machine, almost one eighth of it to the third machine and so on. (We are making sure that each Turing machine in the enumeration gets a known constant fraction range of total run time, assuming we keep running at least till its first transition.)

How can we do that? Example: Simulate one transition of the first machine. Then the same again - one more transition of the first machine. Then one transition of the second machine. Than all this again: two more transitions of the first machine and one more of the second machine. Only then do the first transition of the third machine, followed by all that again (seven more transitions in total) before ever simulating the first transition of the fourth machine.

From time to time, a machine terminates, be it due to its alarm clock or to its having solved its primary problem (which will rarely consist of a production of 3 colorings of the input graph, but who cares). If a machine terminated, we check whether it has produced a valid 3 coloring of the input graph on its output tape, and if so, we terminate the entire simulation of all the Turing machines with attached alarm clocks, returning the same 3 coloring as the output.

To be honest, I haven't closely checked that I can amortize the overhead of switching attention from a machine to a machine, the overhead of iterating across the machines (i.e., generating the initial state of a new machine in the enumeration), and the overhead of checking the terminal states (whether a terminating machine stumbled upon a valid 3 coloring or not); but I can certainly make sure to spend more time on the simulated transitions of individual Turing machines than on all these kinds of overhead, i.e. the total overhead ends up less than 100%, again a constant factor.

Now, it is well known that the function version of the 3 coloring problem is self reducible to its decision version. There's a simple polynomial time algorithm for the decision problem (by P=NP) and therefore the self-reducing algorithm which actually reliably identifies an example 3 coloring in polynomial time whenever one exists, occurs somewhere in our enumeration of all Turing machines - and it occurs somewhere even with a liberal enough polynomial time alarm clock which allows it to complete in whatever time it needs. Good news is that we gave a fixed fraction of attention (of the time resource) to this particular machine in our multitasking simulation, therefore we have slowed it down just by a (huge) constant factor - by the other simultaneously simulated machines, and by the remaining up to 100% overhead. So even this specific "universal" simulation is capable of providing examples of 3 coloring in polynomial time. Quod erat promissum.

===

(I'd love to say that this simulation comes close to preserving even the optimum exponent of finding the 3 coloring, but that just wouldn't be true. The biggest problem in this respect is that the "universal" simulator may have fewer tapes and fewer states than the machine being simulated, and simulating even a single transition is a costly exercise; the simulation preserves polynomial time, but not the specific exponent.)

Unfortunately, any such simulation only becomes a polynomial time algorithm for finding 3-colorings if we now equip it with its own polynomial time alarm clock (thus slowing it down twice, and also guaranteeing that it terminates on any input within the specified time limit); and this last step is con-constructive. Unlike any part of the construction until now, we don't know which polynomial among n, 2*n^2, 3*n^3, ... should be chosen for the alarm clock. We just know that a sufficiently liberal alarm clock exists, such that if we attach it to our (otherwise specific) "universal" machine, we will obtain a polynomial time algorithm doing 3 colorings wherever they exist and rejecting (only) graphs that are not 3 colorable, or inputs that do not encode graphs.

The method of universal simulation can be extended even to your graph coloring problem with the help of the additional technique described in this answer. What gets messier is that we are then no longer able to filter out "wrong answers" that easily; if a machine offers us a 5-coloring, how do we know whether a 4-coloring exists? The sufficient solution is to just wait it out, either a 4-coloring will appear in the output of a better behaved child machine or not, before the master alarm clock runs out. Again, the last step will be non-constructive: we know that with a sufficiently liberal polynomial time alarm clock we'd get a polynomial algorithm giving us optimal colorings, but it's hard to tell which specific polynomial to choose if all we know is that P=NP. If we choose a too aggressive (insufficient) polynomial time alarm clock, not only we will sometimes fail to find the optimal coloring, but we will sometimes output a suboptimal coloring which we tried to wait out, but not patiently enough.

Answer 4

Having P=NP means there is a polynomial time algorithm. It doesn’t mean we know one, or we will ever know one, or we will ever be able to prove it runs in polynomial time.

And we might find there is an algorithm running in O(n^10000), which means we can actually solve no instances of size > 1.