Almost Exact Graph 3-Coloring in O(1.277^n) Time.
Faisal N. Abu-Khzam, Michael Allen Langston · Cologne Twente Workshop on Graphs and Combinatorial Optimization · 2012
Despite super-polynomial-time complexity, exact algorithms forNP-hard problems have recently received a great deal of attention. This can probably be attributed to a variety of factors. Included among them are the emergence of asymptotically efficient methods based on the theory of fixed parameter tractability, the significance of exact solutions in many high-throughput applications, the relative hardness of reasonable polynomial-time approximations, and continuing enhancements in high performance computing access and scalability. In this brief overview, we describe a new algorithm for almost exact graph 3-coloring. Our method’s worst-case running time is O(1.277n). While this improves on the current best 3-coloring bound of O(1.3289n), a tradeoff is that our method may occasionally merely 4-color a 3-colorable graph. Our approach is based on maximal independent set enumeration. Rather than enumerate all maximal independent sets, however, we first restrict our attention to a single minimum vertex cover, which we know contains at most 2n/3 vertices. In what follows we will motivate, present and analyze this new algorithm, and discuss the apparent infrequency with which it fails to produce a minimum coloring. We will also place this work in context, and provide a few future research directions.