Monte Carlo Graph Coloring

• URL: http://arxiv.org/abs/2504.03277v1
• Date: Fri, 04 Apr 2025 08:57:01 GMT
• Title: Monte Carlo Graph Coloring
• Authors: Tristan Cazenave, Benjamin Negrevergne, Florian Sikora,
• Abstract summary: Graph Coloring is probably one of the most studied and famous problem in graph algorithms.<n>We show how to efficiently apply Monte Carlo search to Graph Coloring.
• Score: 3.435169201271934
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Graph Coloring is probably one of the most studied and famous problem in graph algorithms. Exact methods fail to solve instances with more than few hundred vertices, therefore, a large number of heuristics have been proposed. Nested Monte Carlo Search (NMCS) and Nested Rollout Policy Adaptation (NRPA) are Monte Carlo search algorithms for single player games. Surprisingly, few work has been dedicated to evaluating Monte Carlo search algorithms to combinatorial graph problems. In this paper we expose how to efficiently apply Monte Carlo search to Graph Coloring and compare this approach to existing ones.

Related papers

• Monte Carlo Search Algorithms Discovering Monte Carlo Tree Search Exploration Terms [4.561007128508218]
  The optimized Monte Carlo Tree Search algorithms are PUCT and SHUSS. For small search budgets of 32 evaluations the discovered root exploration terms make both algorithms competitive.
  arXiv  Detail & Related papers  (2024-04-14T17:06:20Z)
• Graph Sparsifications using Neural Network Assisted Monte Carlo Tree Search [9.128418945452088]
  We describe an approach for computing graph sparsifiers by combining a graph neural network and Monte Carlo Tree Search. We first train a graph neural network that takes as input a partial solution and proposes a new node to be added as output. This neural network is then used in a Monte Carlo search to compute a sparsifier.
  arXiv  Detail & Related papers  (2023-11-17T03:59:50Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
  arXiv  Detail & Related papers  (2023-07-25T12:33:53Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  We study Grover's search algorithm focusing on continuous-time quantum walk on graphs. Instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph endowed Laplacians.
  arXiv  Detail & Related papers  (2022-07-04T19:33:06Z)
• Refutation of Spectral Graph Theory Conjectures with Monte Carlo Search [4.38602607138044]
  We demonstrate how Monte Carlo Search (MCS) algorithms can be used to build graphs and find counter-examples to spectral graph theory conjectures. We refute a conjecture attributed to Peter Shor that was left open.
  arXiv  Detail & Related papers  (2022-07-04T07:06:48Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• A Grover search-based algorithm for the list coloring problem [1.332560004325655]
  We propose a quantum algorithm based on Grover search to speed up exhaustive search. Our algorithm loses in complexity to classical ones in specific restricted cases, but improves exhaustive search for cases where the lists and graphs considered are arbitrary in nature.
  arXiv  Detail & Related papers  (2021-08-20T08:41:22Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  Data association across frames is at the core of Multiple Object Tracking (MOT) task. Existing methods mostly ignore the context information among tracklets and intra-frame detections. We propose a novel learnable graph matching method to address these issues.
  arXiv  Detail & Related papers  (2021-03-30T08:58:45Z)
• Monte-Carlo Graph Search for AlphaZero [15.567057178736402]
  We introduce a new, improved search algorithm for AlphaZero that generalizes the search tree to a directed acyclic graph. In our evaluations, we use the CrazyAra engine on chess and crazyhouse as examples to show that these changes bring significant improvements to AlphaZero.
  arXiv  Detail & Related papers  (2020-12-20T22:51:38Z)
• Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances [55.64521598173897]
  This paper tries to train a small-scale model, which could be repetitively used to build heat maps for the traveling salesman problem (TSP) Heat maps are fed into a reinforcement learning approach (Monte Carlo tree search) to guide the search of high-quality solutions. Experimental results show that, this new approach clearly outperforms the existing machine learning based TSP algorithms.
  arXiv  Detail & Related papers  (2020-12-19T11:06:30Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)

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.