Solving Hard Computational Problems Efficiently: Asymptotic Parametric Complexity 3-Coloring Algorithm

• Published in: arXiv.org 2012-09
• Main Author: Martin, H Jose Antonio
• Format: Article
• Language: English
• Subjects: Algorithms; Coloring; Combinatorial analysis; Gene sequencing; Genomes; Graphs; Hypotheses; Molecular biology; Optimization; Polynomials
• ISSN: 2331-8422

Many practical problems in almost all scientific and technological disciplines have been classified as computationally hard (NP-hard or even NP-complete). In life sciences, combinatorial optimization problems frequently arise in molecular biology, e.g., genome sequencing; global alignment of multiple genomes; identifying siblings or discovery of dysregulated pathways.In almost all of these problems, there is the need for proving a hypothesis about certain property of an object that can be present only when it adopts some particular admissible structure (an NP-certificate) or be absent (no admissible structure), however, none of the standard approaches can discard the hypothesis when no solution can be found, since none can provide a proof that there is no admissible structure. This article presents an algorithm that introduces a novel type of solution method to "efficiently" solve the graph 3-coloring problem; an NP-complete problem. The proposed method provides certificates (proofs) in both cases: present or absent, so it is possible to accept or reject the hypothesis on the basis of a rigorous proof. It provides exact solutions and is polynomial-time (i.e., efficient) however parametric. The only requirement is sufficient computational power, which is controlled by the parameter \(\alpha\in\mathbb{N}\). Nevertheless, here it is proved that the probability of requiring a value of \(\alpha>k\) to obtain a solution for a random graph decreases exponentially: \(P(\alpha>k) \leq 2^{-(k+1)}\), making tractable almost all problem instances. Thorough experimental analyses were performed. The algorithm was tested on random graphs, planar graphs and 4-regular planar graphs. The obtained experimental results are in accordance with the theoretical expected results.