arXiv:2102.07089

Simple vertex coloring algorithms

Morris, Jackson, Fang Song

Published Feb 14, 2021• 0 citations

Abstract

Given a graph $G$ with $n$ vertices and maximum degree $Δ$, it is known that $G$ admits a vertex coloring with $Δ+ 1$ colors such that no edge of $G$ is monochromatic. This can be seen constructively by a simple greedy algorithm, which runs in time $O(nΔ)$. Very recently, a sequence of results (e.g., [Assadi et. al. SODA'19, Bera et. al. ICALP'20, Alon Assadi Approx/Random'20]) show randomized algorithms for $(ε+ 1)Δ$-coloring in the query model making $\tilde{O}(n\sqrt{n})$ queries, improving over the greedy strategy on dense graphs. In addition, a lower bound of $Ω(n\sqrt n)$ for any $O(Δ)$-coloring is established on general graphs. In this work, we give a simple algorithm for $(1 + ε)Δ$-coloring. This algorithm makes $O(ε^{-1/2}n\sqrt{n})$ queries, which matches the best existing algorithms as well as the classical lower bound for sufficiently large $ε$. Additionally, it can be readily adapted to a quantum query algorithm making $\tilde{O}(ε^{-1}n^{4/3})$ queries, bypassing the classical lower bound. Complementary to these algorithmic results, we show a quantum lower bound of $Ω(n)$ for $O(Δ)$-coloring.

DOI: 10.48550/arxiv.2102.07089

Related papers

Quantum Query Complexity of Maximum Degree and its Generalizations

Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro +1 more

quant-pharXiv:2610.13906Oct 12, 20260 citations

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring

Asaf Ferber, Liam Hardiman, Xiaonan Chen

arXiv:2502.06024Feb 9, 20250 citations

Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem

Cheng Xin

quant-pharXiv:2609.05812Sep 8, 20260 citations

A quantum algorithm for learning a graph of bounded degree

Asaf Ferber, Liam Hardiman

arXiv:2402.18714Feb 28, 20240 citations

A Grover Search-Based Algorithm for the List Coloring Problem

Sayan Mukherjee

arXiv:2108.09061IEEE Transactions on Quantum EngineeringJan 1, 202225 citations

Edge coloring lattice graphs

Joris Kattemölle

arXiv:2402.08752Journal of Mathematical PhysicsMay 1, 20253 citations

arXiv:2102.07089

Simple vertex coloring algorithms

Morris, Jackson, Fang Song

Published Feb 14, 2021• 0 citations

arXiv HTML PDF

Abstract

Given a graph

G

with

n

vertices and maximum degree

Δ

, it is known that

G

admits a vertex coloring with

Δ+ 1

colors such that no edge of

G

is monochromatic. This can be seen constructively by a simple greedy algorithm, which runs in time

O(nΔ)

. Very recently, a sequence of results (e.g., [Assadi et. al. SODA'19, Bera et. al. ICALP'20, Alon Assadi Approx/Random'20]) show randomized algorithms for

(ε+ 1)Δ

-coloring in the query model making

\tilde{O}(n\sqrt{n})

queries, improving over the greedy strategy on dense graphs. In addition, a lower bound of

Ω(n\sqrt n)

for any

O(Δ)

-coloring is established on general graphs. In this work, we give a simple algorithm for

(1 + ε)Δ

-coloring. This algorithm makes

O(ε^{-1/2}n\sqrt{n})

queries, which matches the best existing algorithms as well as the classical lower bound for sufficiently large

ε

. Additionally, it can be readily adapted to a quantum query algorithm making

\tilde{O}(ε^{-1}n^{4/3})

queries, bypassing the classical lower bound. Complementary to these algorithmic results, we show a quantum lower bound of

Ω(n)

for

O(Δ)

-coloring.

DOI: 10.48550/arxiv.2102.07089

Related papers

Quantum Query Complexity of Maximum Degree and its Generalizations

Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro +1 more

We study the quantum query complexity of several basic graph problems. 1) We prove a tight $Θ(n^{3/2})$ bound for finding a maximum-out-degree vertex in an $n$ -vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an $n$ -vertex undirected graph requires $Θ(n^{3/2})$ quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum $(k,n-k)$ -Cut, which asks for the largest cut with one side of size $k$ . For every constant $k\geq 1$ , we give an $O(n^{2-1/(k+1)})$ -query quantum algorithm. 4) We establish a reduction to Maximum $(k,n-k)$ -Cut involving $k$ -Graph Collision, which asks whether the marked vertices of a known graph contain a $k$ -clique. For $k\geq 3$ , this yields unconditional lower bounds with exponents strictly larger than $3/2$ , showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for $k$ -Graph Collision, the reduction yields a lower bound matching our upper bound above.We study the quantum query complexity of several basic graph problems. 1) We prove a tight $Θ(n^{3/2})$ bound for finding a maximum-out-degree vertex in an $n$-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an $n$-vertex undirected graph requires $Θ(n^{3/2})$ quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum $(k,n-k)$-Cut, which asks for the largest cut with one side of size $k$. For every constant $k\geq 1$, we give an $O(n^{2-1/(k+1)})$-query quantum algorithm. 4) We establish a reduction to Maximum $(k,n-k)$-Cut involving $k$-Graph Collision, which asks whether the marked vertices of a known graph contain a $k$-clique. For $k\geq 3$, this yields unconditional lower bounds with exponents strictly larger than $3/2$, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for $k$-Graph Collision, the reduction yields a lower bound matching our upper bound above.

quant-pharXiv:2610.13906Oct 12, 20260 citations

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring

Asaf Ferber, Liam Hardiman, Xiaonan Chen

We present three sublinear randomized algorithms for vertex-coloring of graphs with maximum degree $Δ$ . The first is a simple algorithm that extends the idea of Morris and Song to color graphs with maximum degree $Δ$ using $Δ+1$ colors. Combined with the greedy algorithm, it achieves an expected runtime of $O(n^{3/2}\sqrt{\log n})$ in the query model, improving on Assadi, Chen, and Khanna's algorithm by a $\sqrt{\log n}$ factor in expectation. When we allow quantum queries to the graph, we can accelerate the first algorithm using Grover's famous algorithm, resulting in a runtime of $\tilde{O}(n^{4/3})$ quantum queries. Finally, we introduce a quantum algorithm for $(1+ε)Δ$ -coloring, achieving $O(ε^{-1}n^{5/4}\log^{3/2}n)$ quantum queries, offering a polynomial improvement over the previous best bound by Morris and Song.We present three sublinear randomized algorithms for vertex-coloring of graphs with maximum degree $Δ$. The first is a simple algorithm that extends the idea of Morris and Song to color graphs with maximum degree $Δ$ using $Δ+1$ colors. Combined with the greedy algorithm, it achieves an expected runtime of $O(n^{3/2}\sqrt{\log n})$ in the query model, improving on Assadi, Chen, and Khanna's algorithm by a $\sqrt{\log n}$ factor in expectation. When we allow quantum queries to the graph, we can accelerate the first algorithm using Grover's famous algorithm, resulting in a runtime of $\tilde{O}(n^{4/3})$ quantum queries. Finally, we introduce a quantum algorithm for $(1+ε)Δ$-coloring, achieving $O(ε^{-1}n^{5/4}\log^{3/2}n)$ quantum queries, offering a polynomial improvement over the previous best bound by Morris and Song.

arXiv:2502.06024Feb 9, 20250 citations

Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem

Cheng Xin

The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an $N$ -vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every $K\ge2$ and $N\ge4^{K-1}$ , finds and verifies a homogeneous $K$ -set using $O\!\left(2^K K\log\frac Kη\right)$ edge queries with failure probability at most $η$ . At the Ramsey scale $N=2^n$ , this yields a homogeneous set of order $\lfloor n/2\rfloor+1$ using $O(\sqrt N\log N\log(\log N/η))$ queries, improving on the $O(N)$ queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an $Ω(N^{1/12})$ quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an $Ω(N^{1-1/\sqrt2})$ randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution $G(N,1/2)$ . On that distribution a greedy quantum search uses only $\widetilde O(N^{1/4})$ queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an $N$-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every $K\ge2$ and $N\ge4^{K-1}$, finds and verifies a homogeneous $K$-set using $O\!\left(2^K K\log\frac Kη\right)$ edge queries with failure probability at most $η$. At the Ramsey scale $N=2^n$, this yields a homogeneous set of order $\lfloor n/2\rfloor+1$ using $O(\sqrt N\log N\log(\log N/η))$ queries, improving on the $O(N)$ queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an $Ω(N^{1/12})$ quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an $Ω(N^{1-1/\sqrt2})$ randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution $G(N,1/2)$. On that distribution a greedy quantum search uses only $\widetilde O(N^{1/4})$ queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.

quant-pharXiv:2609.05812Sep 8, 20260 citations

A quantum algorithm for learning a graph of bounded degree

Asaf Ferber, Liam Hardiman

We are presented with a graph, $G$ , on $n$ vertices with $m$ edges whose edge set is unknown. Our goal is to learn the edges of $G$ with as few queries to an oracle as possible. When we submit a set $S$ of vertices to the oracle, it tells us whether or not $S$ induces at least one edge in $G$ . This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of $O(m \log n)$ for a general graph $G$ with $m$ edges. When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where $G$ has maximum degree $d$ and is $O(1)$ -colorable, Montanaro and Shao presented an algorithm that learns the edges of $G$ in at most $\tilde{O}(d^2m^{3/4})$ quantum queries. This gives an upper bound of $\tilde{O}(m^{3/4})$ quantum queries when $G$ is a matching or a Hamiltonian cycle, which is far away from the lower bound of $Ω(\sqrt{m})$ queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where $G$ has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in $\tilde{O}(\sqrt{m})$ quantum queries, matching the theoretical lower bound up to logarithmic factors.We are presented with a graph, $G$, on $n$ vertices with $m$ edges whose edge set is unknown. Our goal is to learn the edges of $G$ with as few queries to an oracle as possible. When we submit a set $S$ of vertices to the oracle, it tells us whether or not $S$ induces at least one edge in $G$. This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of $O(m \log n)$ for a general graph $G$ with $m$ edges. When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where $G$ has maximum degree $d$ and is $O(1)$-colorable, Montanaro and Shao presented an algorithm that learns the edges of $G$ in at most $\tilde{O}(d^2m^{3/4})$ quantum queries. This gives an upper bound of $\tilde{O}(m^{3/4})$ quantum queries when $G$ is a matching or a Hamiltonian cycle, which is far away from the lower bound of $Ω(\sqrt{m})$ queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where $G$ has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in $\tilde{O}(\sqrt{m})$ quantum queries, matching the theoretical lower bound up to logarithmic factors.

arXiv:2402.18714Feb 28, 20240 citations

A Grover Search-Based Algorithm for the List Coloring Problem

Sayan Mukherjee

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\geq 5$ . The list coloring problem asks the following more general question: given alistof available colors for each vertex in a graph, does it admit a proper coloring? We propose a hybrid classical-quantum algorithm based on Grover search 12 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.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\geq 5$. The list coloring problem asks the following more general question: given alistof available colors for each vertex in a graph, does it admit a proper coloring? We propose a hybrid classical-quantum algorithm based on Grover search 12 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.

arXiv:2108.09061IEEE Transactions on Quantum EngineeringJan 1, 202225 citations

Edge coloring lattice graphs

Joris Kattemölle

We develop the theory of the edge coloring of lattice graphs. A central role is played by a necessary and sufficient condition for a proper edge coloring of a patch of a lattice graph to induce a proper edge coloring of the entire lattice graph by translation. Using this condition, we introduce a method that finds nearly minimal or minimal edge colorings of lattice graphs. For a nearly minimal edge coloring, the running time is O(μ2D4), where μ is the number of edges in one cell (or “basis graph”) of the lattice graph and D is the maximum distance between two cells connected by an edge. Crucially, this complexity depends only on local properties of the lattice graph, making it independent of the total graph size. As a result, the method applies even to infinite lattice graphs with finite maximum degree. For minimal edge coloring, we lack a rigorous upper bound on the running time, which we find poses no limitation in practice; we use the method to minimally edge color the meshes of all k-uniform tilings of the plane for k ≤ 6 with modest computational resources. We find that all these lattice graphs belong to Vizing class I. By relating edge colorings to quantum circuits, our work has direct applications in quantum computation, including quantum simulation of condensed matter, cluster-state preparation, error characterization, and error correction.We develop the theory of the edge coloring of lattice graphs. A central role is played by a necessary and sufficient condition for a proper edge coloring of a patch of a lattice graph to induce a proper edge coloring of the entire lattice graph by translation. Using this condition, we introduce a method that finds nearly minimal or minimal edge colorings of lattice graphs. For a nearly minimal edge coloring, the running time is O(μ2D4), where μ is the number of edges in one cell (or “basis graph”) of the lattice graph and D is the maximum distance between two cells connected by an edge. Crucially, this complexity depends only on local properties of the lattice graph, making it independent of the total graph size. As a result, the method applies even to infinite lattice graphs with finite maximum degree. For minimal edge coloring, we lack a rigorous upper bound on the running time, which we find poses no limitation in practice; we use the method to minimally edge color the meshes of all k-uniform tilings of the plane for k ≤ 6 with modest computational resources. We find that all these lattice graphs belong to Vizing class I. By relating edge colorings to quantum circuits, our work has direct applications in quantum computation, including quantum simulation of condensed matter, cluster-state preparation, error characterization, and error correction.

arXiv:2402.08752Journal of Mathematical PhysicsMay 1, 20253 citations

Given a graph

G

with

n

vertices and maximum degree

Δ

, it is known that

G

admits a vertex coloring with

Δ+ 1

colors such that no edge of

G

is monochromatic. This can be seen constructively by a simple greedy algorithm, which runs in time

O(nΔ)

. Very recently, a sequence of results (e.g., [Assadi et. al. SODA'19, Bera et. al. ICALP'20, Alon Assadi Approx/Random'20]) show randomized algorithms for

(ε+ 1)Δ

-coloring in the query model making

\tilde{O}(n\sqrt{n})

queries, improving over the greedy strategy on dense graphs. In addition, a lower bound of

Ω(n\sqrt n)

for any

O(Δ)

-coloring is established on general graphs. In this work, we give a simple algorithm for

(1 + ε)Δ

-coloring. This algorithm makes

O(ε^{-1/2}n\sqrt{n})

queries, which matches the best existing algorithms as well as the classical lower bound for sufficiently large

ε

. Additionally, it can be readily adapted to a quantum query algorithm making

\tilde{O}(ε^{-1}n^{4/3})

queries, bypassing the classical lower bound. Complementary to these algorithmic results, we show a quantum lower bound of

Ω(n)

for

O(Δ)

-coloring.

We study the quantum query complexity of several basic graph problems. 1) We prove a tight

Θ(n^{3/2})

bound for finding a maximum-out-degree vertex in an

n

-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an

n

-vertex undirected graph requires

Θ(n^{3/2})

quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum

(k,n-k)

-Cut, which asks for the largest cut with one side of size

k

. For every constant

k\geq 1

, we give an

O(n^{2-1/(k+1)})

-query quantum algorithm. 4) We establish a reduction to Maximum

(k,n-k)

-Cut involving

k

-Graph Collision, which asks whether the marked vertices of a known graph contain a

k

-clique. For

k\geq 3

, this yields unconditional lower bounds with exponents strictly larger than

3/2

, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for

k

-Graph Collision, the reduction yields a lower bound matching our upper bound above.

We present three sublinear randomized algorithms for vertex-coloring of graphs with maximum degree

Δ

. The first is a simple algorithm that extends the idea of Morris and Song to color graphs with maximum degree

Δ

using

Δ+1

colors. Combined with the greedy algorithm, it achieves an expected runtime of

O(n^{3/2}\sqrt{\log n})

in the query model, improving on Assadi, Chen, and Khanna's algorithm by a

\sqrt{\log n}

factor in expectation. When we allow quantum queries to the graph, we can accelerate the first algorithm using Grover's famous algorithm, resulting in a runtime of

\tilde{O}(n^{4/3})

quantum queries. Finally, we introduce a quantum algorithm for

(1+ε)Δ

-coloring, achieving

O(ε^{-1}n^{5/4}\log^{3/2}n)

quantum queries, offering a polynomial improvement over the previous best bound by Morris and Song.

The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an

N

-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every

K\ge2

and

N\ge4^{K-1}

, finds and verifies a homogeneous

K

-set using

O\!\left(2^K K\log\frac Kη\right)

edge queries with failure probability at most

η

. At the Ramsey scale

N=2^n

, this yields a homogeneous set of order

\lfloor n/2\rfloor+1

using

O(\sqrt N\log N\log(\log N/η))

queries, improving on the

O(N)

queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an

Ω(N^{1/12})

quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an

Ω(N^{1-1/\sqrt2})

randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution

G(N,1/2)

. On that distribution a greedy quantum search uses only

\widetilde O(N^{1/4})

queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.

We are presented with a graph,

G

, on

n

vertices with

m

edges whose edge set is unknown. Our goal is to learn the edges of

G

with as few queries to an oracle as possible. When we submit a set

S

of vertices to the oracle, it tells us whether or not

S

induces at least one edge in

G

. This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of

O(m \log n)

for a general graph

G

with

m

edges. When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where

G

has maximum degree

d

and is

O(1)

-colorable, Montanaro and Shao presented an algorithm that learns the edges of

G

in at most

\tilde{O}(d^2m^{3/4})

quantum queries. This gives an upper bound of

\tilde{O}(m^{3/4})

quantum queries when

G

is a matching or a Hamiltonian cycle, which is far away from the lower bound of

Ω(\sqrt{m})

queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where

G

has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in

\tilde{O}(\sqrt{m})

quantum queries, matching the theoretical lower bound up to logarithmic factors.

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\geq 5

. The list coloring problem asks the following more general question: given alistof available colors for each vertex in a graph, does it admit a proper coloring? We propose a hybrid classical-quantum algorithm based on Grover search 12 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.