HyColor: An Efficient Heuristic Algorithm for Graph Coloring

• URL: http://arxiv.org/abs/2506.07373v1
• Date: Mon, 09 Jun 2025 02:45:08 GMT
• Title: HyColor: An Efficient Heuristic Algorithm for Graph Coloring
• Authors: Enqiang Zhu, Yu Zhang, Haopeng Sun, Ziqi Wei, Witold Pedrycz, Chanjuan Liu, Jin Xu,
• Abstract summary: This paper presents an efficient hybrid algorithm for the graph coloring problem (GCP) named HyColor.<n>HyColor excels in handling large-scale sparse graphs while achieving impressive results on small dense graphs.
• Score: 44.95631305040251
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The graph coloring problem (GCP) is a classic combinatorial optimization problem that aims to find the minimum number of colors assigned to vertices of a graph such that no two adjacent vertices receive the same color. GCP has been extensively studied by researchers from various fields, including mathematics, computer science, and biological science. Due to the NP-hard nature, many heuristic algorithms have been proposed to solve GCP. However, existing GCP algorithms focus on either small hard graphs or large-scale sparse graphs (with up to 10^7 vertices). This paper presents an efficient hybrid heuristic algorithm for GCP, named HyColor, which excels in handling large-scale sparse graphs while achieving impressive results on small dense graphs. The efficiency of HyColor comes from the following three aspects: a local decision strategy to improve the lower bound on the chromatic number; a graph-reduction strategy to reduce the working graph; and a k-core and mixed degree-based greedy heuristic for efficiently coloring graphs. HyColor is evaluated against three state-of-the-art GCP algorithms across four benchmarks, comprising three large-scale sparse graph benchmarks and one small dense graph benchmark, totaling 209 instances. The results demonstrate that HyColor consistently outperforms existing heuristic algorithms in both solution accuracy and computational efficiency for the majority of instances. Notably, HyColor achieved the best solutions in 194 instances (over 93%), with 34 of these solutions significantly surpassing those of other algorithms. Furthermore, HyColor successfully determined the chromatic number and achieved optimal coloring in 128 instances.

Related papers

• Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach [0.0]
  edge-colored clustering (ECC) has emerged as a useful approach for handling categorical data.<n>To tackle these limitations, three versions of ECC have been studied.<n>We present an algorithmic framework that combines the strengths of LP with the computational efficiency of algorithms.
  arXiv  Detail & Related papers  (2025-05-23T15:46:16Z)
• Efficient hybrid variational quantum algorithm for solving graph coloring problem [4.4739537033766705]
  This paper proposes a hybrid variational quantum algorithm to solve the $k$-coloring problem of graph vertices.<n>We employ a hierarchical framework that integrates feedback correction and conflict resolution to achieve $k$-coloring.<n>We apply the proposed algorithm to optimize the scheduling of a subway transportation network, demonstrating a high degree of fairness.
  arXiv  Detail & Related papers  (2025-04-30T05:45:15Z)
• An island-parallel ensemble metaheuristic algorithm for large graph coloring problems [0.4915744683251149]
  We propose a new island-parallel ensemble metaheuristic algorithm (PEM-Color) to solve large GCP instances.<n>To the best of our knowledge, this is the first study that combines metaheuristics and applies to the GCP using an ensemble approach.
  arXiv  Detail & Related papers  (2025-04-21T13:15:23Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC.<n>It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters.<n>GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• Fast Semi-supervised Learning on Large Graphs: An Improved Green-function Method [93.04936336359502]
  In graph-based semi-supervised learning, the Green-function method is a classical method that works by computing the Green's function in the graph space. We make a detailed analysis on it and propose a novel method from the perspective of optimization. Unlike the original method, our improved method can also apply two accelerating techniques, Gaussian Elimination, and Anchored Graphs.
  arXiv  Detail & Related papers  (2024-11-04T04:27:18Z)
• Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs [0.0]
  We present a novel algorithm that leverages graph neural networks to tackle the problem efficiently, particularly for large graphs. We demonstrate the effectiveness of our method on a dataset of Erdos-Renyi graphs, showing its applicability also in hard-to-solve connectivity regions.
  arXiv  Detail & Related papers  (2024-08-02T18:02:51Z)
• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  The ubiquity of large-scale graphs in node-classification tasks hinders the real-world applications of Graph Neural Networks (GNNs) This paper studies graph coresets for GNNs and avoids the interdependence issue by selecting ego-graphs based on their spectral embeddings. Our spectral greedy graph coreset (SGGC) scales to graphs with millions of nodes, obviates the need for model pre-training, and applies to low-homophily graphs.
  arXiv  Detail & Related papers  (2024-05-27T17:52:12Z)
• Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [49.41718583061147]
  Graph condensation is a data-centric solution to replace the large graph with a small yet informative condensed graph.<n>Existing GC methods suffer from intricate optimization processes, necessitating excessive computing resources and training time.<n>We propose a training-free GC framework termed Class-partitioned Graph Condensation (CGC)<n>CGC condenses the Ogbn-products graph within 30 seconds, achieving a speedup ranging from $102$X to $104$X and increasing accuracy by up to 4.2%.
  arXiv  Detail & Related papers  (2024-05-22T14:57:09Z)
• GraphCoCo: Graph Complementary Contrastive Learning [65.89743197355722]
  Graph Contrastive Learning (GCL) has shown promising performance in graph representation learning (GRL) without the supervision of manual annotations. This paper proposes an effective graph complementary contrastive learning approach named GraphCoCo to tackle the above issue.
  arXiv  Detail & Related papers  (2022-03-24T02:58:36Z)
• Evolutionary Algorithm for Graph Coloring Problem [0.0]
  The graph coloring problem (GCP) is one of the most studied NP-HARD problems in computer science. In our paper, we start with the theoretical upper bound of chromatic number, that is, maximum out-degree + 1. In the process of evolution some of the colors are made unused to dynamically reduce the number of color in every generation.
  arXiv  Detail & Related papers  (2021-11-17T12:16:57Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  We present the PPRGo model which utilizes an efficient approximation of information diffusion in GNNs. In addition to being faster, PPRGo is inherently scalable, and can be trivially parallelized for large datasets like those found in industry settings. We show that training PPRGo and predicting labels for all nodes in this graph takes under 2 minutes on a single machine, far outpacing other baselines on the same graph.
  arXiv  Detail & Related papers  (2020-07-03T09:30:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.