2026-07-22T18:34:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21174 2024-09-23T09:13:18Z ddc:004 open_access

A Faster Algorithm for the 4-Coloring Problem Wu, Pu Gu, Huanyu Jiang, Huiqin Shao, Zehui Xu, Jin Graph coloring Graph algorithms Exact algorithms We explore the 4-coloring problem, a fundamental combinatorial NP-hard problem. Given a graph G, the 4-coloring problem asks whether there exists a function f from the vertex set of G to {1,2,3,4} such that f(u)≠ f(v) for each edge uv of G. Such function f is referred to as a 4-coloring of G. The fastest known algorithm for the 4-coloring problem, introduced by Fomin, Gaspers, and Saurabh (COCOON 2007), exhibits a time complexity of O(1.7272ⁿ) and exponential space. In this paper, we propose an enhanced algorithm for the 4-coloring problem with a time complexity of O(1.7159ⁿ) and polynomial space. Our algorithm is deterministic and built upon a novel method. Specifically, inspired by previous algorithmic approaches for the 4-coloring problem, such as the aforementioned O(1.7272ⁿ) time algorithm, we consider the instance (G,I,S), where G is a graph and I,S are subsets of its vertex set representing vertices colored with 1 and vertices unable to be colored with 1, respectively. For a given instance (G,I,S), we aim to determine the existence of a 4-coloring f of G such that f(v) = 1 for v ∈ I and f(v)≠ 1 for v ∈ S. Our key innovation lies in recognizing that, leveraging certain combinatorial properties, the instance (G,I,S) can be efficiently solved when G-I-S is a union of K₃’s and K₄’s (where K₃ and K₄ denote complete graphs with 3 and 4 vertices, respectively). The ability to efficiently solve instances (G,I,S), where G-I-S is comprised solely of K₃’s and K₄’s, enables us to devise a branching algorithm capable of efficiently addressing instances (G,I,S), where G-I-S is not a union of K₃’s and K₄’s (the other case). Based on this innovative method, we derive our final enhanced algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pu Wu and Huanyu Gu and Huiqin Jiang and Zehui Shao and Jin Xu 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.103 urn:nbn:de:0030-drops-211749 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.103 eng https://creativecommons.org/licenses/by/4.0/legalcode