Four color theorem: A fast algorithm


I have implemented an algorithm that goes really fast coloring the edges of a planar graph.

See this video and then try it youself!

Note about the Python program: To try the Python program you need to have Sage. Follow Sage instructions to install it on your computer: http://www.sagemath.org.

The algorithm considers Tait edge coloring and the equivalency of the 3-edge-coloring (known as Tait coloring) and the 4-face-coloring (the original four color theorem for maps).

The algorithm goes like this:

  • It uses a modified Kempe reduction method: it does not shrink a face (faces <= F5) down to a point, but removes a single edge from it (from faces <= F5)
  • It uses a modified Kempe chain edge color switching: when restoring edges from the reduced graph, it will swap half of the colored Kempe loop

Note that while rebuilding a map, all Kempe chains are actually Kempe loops!!!

These are the stats:

  • 100 – 196 vertices, 294 edges = 0 seconds
  • 200 – 396 vertices, 594 edges = 1 seconds
  • 300 – 596 vertices, 894 edges = 4 seconds
  • 400 – 796 vertices, 1194 edges = 6 seconds
  • 500 – 996 vertices, 1494 edges = 8 seconds
  • 600 – 1196 vertices, 1794 edges = 10 seconds
  • 700 – 1396 vertices, 2094 edges = 16 seconds
  • 800 – 1596 vertices, 2394 edges = 18 seconds
  • 900 – 1796 vertices, 2694 edges = 22 seconds
  • 1000 – 1996 vertices, 2994 edges = 26 seconds

Almost linear … what do you think?

The first column is the original number of vertices for the planar triangulation from which the dual graph (a cubic planar graph) is computed. The seconds reported above do not consider the time to load or create the imput graph and to compute the planar embedding. You can also upload an already planar embedded graph using the -p option.

The same problem of coloring the egdes using the Sage function edge_coloring() requires very long time. I run 15 tests, and to color random graphs with 196 vertices and 294 edges, took: 7, 73, 54, 65, 216, 142, 15, 14, 21, 73, 24, 15, 32, 72, 232 seconds, for the same case where my algorithm takes less than 1 second: 100 – 196 vertices, 294 edges.

For the F5 case which requires the adjustments, I tried the following:

  • I tried to swap colors on a local Kempe loop, starting from an edge belonging to the face to restore (local)
    • It does not always work and for particular cases the algorithm can loop forever
  • I tried to swap colors on a Kempe loop along the edges of one of the two main loops at e1 or e2 (the two edges where the edge to restore ends),
    • It does not always work and for particular cases the algorithm can loop forever
  • I tried to swap colors on random Kempe loops around the map
    • It always works (so far) and these adjustments (Kempe loop color switches) are rare

The only (!?!?!?!?) thing that needs to be proved is that random switches of colors of Kempe loops is always possible to solve any type of impasse. I mean, for now I’m dealing with random attemps, I need to understand how the Kempe loops are related to each other and then find a way to know on which one I need to swap colors.

Something I need to modify about the Python program:

  • Read planar embedded graphs as Python list of lists of tuple: [[()()][()()()][()()()]]
    • [[(1542, 1545), (1545, 1787), (1787, 1542)]
      [(1389, 1347), (1347, 1348), (1348, 1389)]
      [(466, 468), (468, 712), (712, 466)]
      [(1398, 1399), (1399, 1401), (1401, 1398)]
      [(467, 423), (423, 428), (428, 467)]
      [(1407, 1404), (1404, 1405), (1405, 1407)]
      [(1644, 1645), (1645, 1690), (1690, 1644)],…]

I am also looking for faster algorithms around:

Here is the example of a colored planar graph with 1996 vertices and 2994 edges:

test-1996-vertices-2994-edges

sage 4ct.py -r 100 -o test-196 (sage)

dot -Tpng test-196.dot -o test-196.png (graphwiz)

Advertisements
This entry was posted in math. Bookmark the permalink.

One Response to Four color theorem: A fast algorithm

  1. Pingback: Four color theorem: A fast algorithm – 2 | Four color theorem

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s