Related papers: A Grover search-based algorithm for the list coloring problem

A Grover search-based algorithm for the list coloring problem

URL: http://arxiv.org/abs/2108.09061v2
Date: Thu, 3 Mar 2022 13:38:04 GMT
Title: A Grover search-based algorithm for the list coloring problem
Authors: Sayan Mukherjee
Abstract summary: 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.
Score: 1.332560004325655
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Graph coloring is a computationally difficult problem, and currently the best known classical algorithm for $k$-coloring of graphs on $n$ vertices has runtimes $\Omega(2^n)$ for $k\ge 5$. The list coloring problem asks the following more general question: given a list of available colors for each vertex in a graph, does it admit a proper coloring? We propose a quantum algorithm based on Grover search to quadratically 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.

Related papers

A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
arXiv Detail & Related papers (2024-02-09T19:01:48Z)
Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms [56.08144272945755]
We compare 8 popular numerical black-box optimization algorithms on the $L_infty$ star discrepancy problem. We show that all used solvers perform very badly on a large majority of the instances. We suspect that state-of-the-art numerical black-box optimization techniques fail to capture the global structure of the problem.
arXiv Detail & Related papers (2023-06-29T14:57:56Z)
Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
We study high-probability regret bounds for adversarial $K$-armed bandits with time-varying feedback graphs over $T$ rounds. We develop an algorithm that achieves the optimal regret $widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$ with high probability. We also develop the first algorithm that achieves the optimal high-probability regret bound for weakly observable graphs.
arXiv Detail & Related papers (2022-10-04T04:36:15Z)
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)
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)
Withdrawn: A Measurement-based Algorithm for Graph Colouring [0.5482532589225553]
In a previous version of this document we misinterpreted the runtime of a part of the described algorithm. We present a novel algorithmic approach to find a proper colouring of a graph with $d$ colours, if it exists.
arXiv Detail & Related papers (2021-11-29T09:17:34Z)
A deep learning guided memetic framework for graph coloring problems [15.426481600285724]
We present a new framework which combines a deep neural network with the best tools of "classical" metaheuristics for graph coloring. A study of the contribution of deep learning in the algorithm highlights that it is possible to learn relevant patterns useful to obtain better solutions to this problem.
arXiv Detail & Related papers (2021-09-13T13:17:41Z)
Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem [15.45783225341009]
We study the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized searchs to recompute high quality solutions.
arXiv Detail & Related papers (2021-05-26T13:00:31Z)
Simple vertex coloring algorithms [2.8808678188754637]
We give a simple algorithm for $(1 + epsilon)Delta$-coloring. It can be adapted to a quantum query algorithm making $tildeO(epsilon-1n4/3)$ queries.
arXiv Detail & Related papers (2021-02-14T07:27:10Z)
Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
We show how to apply the quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph. We construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs.
arXiv Detail & Related papers (2020-11-26T18:22:21Z)
A Query-Efficient Quantum Algorithm for Maximum Matching on General Graphs [0.0]
We design quantum algorithms for maximum matching. In particular, for a graph with $n$ nodes and $m$ edges, our algorithm makes $O(n7/4) queries in the matrix model.
arXiv Detail & Related papers (2020-10-05T20:34:39Z)

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