Newsgroups: sci.math From: christian.bau@isltd.insignia.com (Christian Bau) Subject: Re: Is Map Coloring NP-complete? Date: Mon, 9 Feb 1998 13:08:06 GMT In article <34D99476.2C5C4386@science.unitn.it>, Mauro Brunato wrote: > harden wrote: > > > Given a map on the Euclidean plane with regions with no overlap, it is > > colorable with 4 colors by the 4-color map theorem. Is finding a > > coloring of the map with 4 colors an NP-complete problem( it is in NP > > and it can be done in exponential time )? > > Be careful: your definition of NP-complete problems is wrong. Indeed, > we are unable to prove the existence of NP problems that can't be done > in polynomial time. A better definition is > > A definition that better applies to function problems (those that require > more than a simple "yes/no" answer) is "NP-hard", meaning "at least as hard > as any NP problem", but possibly more. I asked the same question here a while ago (out of curiosity). I was told there are algorithms that can find a four-colouring of any map in polynomial time; actually in O (n^4) where n is the size of the map with an old algorithm and faster with some newer algorithm. The problem of finding the minimum number of colors is NP-complete (proving that three colors are enough instead of four), which means the problem of finding a coloring with the minimum number of colors is NP-hard. ============================================================================== From: kubo@jacobi.math.brown.edu (Tal Kubo) Newsgroups: sci.math Subject: Re: Is Map Coloring NP-complete? Date: 13 Feb 1998 03:57:03 GMT Christian Bau wrote: >The problem of finding the minimum number of colors is NP-complete >(proving that three colors are enough instead of four), which means the >problem of finding a coloring with the minimum number of colors is >NP-hard. Graph 3-Colorability is one of the "Top 10" NP-complete problems like Hamiltonian circuit, 3SAT, vertex cover, etc that are used as bases for proving other problems NP-complete. Planar Graph 3-Colorability is no easier, as there is a "crossover" gadget (a known planar graph with 2 pairs of opposite vertices that must share the same color in any 3-coloring) that one can substitute for the crossings in a given non-planar graph without affecting the structure of a 3-coloring. 1- and 2-colorability (and planarity) are easy to test, and as you mentioned, the proofs of the 4 Color Theorem imply polynomial time algorithms for finding 4-colorings. ============================================================================== From: "Le JyBy (Jeremy Barbay)" Newsgroups: sci.math Subject: Re: Is Map Coloring NP-complete? Date: Fri, 13 Feb 1998 10:06:35 +0100 Hi ! Graph 3-colorability is a well known NP-Complete problem.(Which means I thinck that k-colorability can be reduced to 3-colorability) But also, if you study Average Complexity of algorithm, it have been proved that you can solve 3-colorability in linear (or was it constant ?) time ON AVERAGE (using uniform probability ob graphs) by searching 4Clicks. In fact, as very few Graphs are 3 colorable, and 4Cliques very frequents in graph no-3-colorable, you can very queeckly determine if a graph is NO 3-colorable, and it'll take more time to prove that it isn't. Have a nice day ! -- Le JyBy French student in mathematics and computer science. I shall try to start an thesis in computer science next year. Curently working on Evolution Algorithm, in search of an explanation to their success (determining sub-classes and all that mess...)