Simple vertex coloring algorithms

• URL: http://arxiv.org/abs/2102.07089v1
• Date: Sun, 14 Feb 2021 07:27:10 GMT
• Title: Simple vertex coloring algorithms
• Authors: Jackson Morris and Fang Song
• Abstract summary: 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.
• Score: 2.8808678188754637
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a graph $G$ with $n$ vertices and maximum degree $\Delta$, it is known that $G$ admits a vertex coloring with $\Delta + 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\Delta)$. 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 $(\epsilon + 1)\Delta$-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 $\Omega(n\sqrt n)$ for any $O(\Delta)$-coloring is established on general graphs. In this work, we give a simple algorithm for $(1 + \epsilon)\Delta$-coloring. This algorithm makes $O(\epsilon^{-1/2}n\sqrt{n})$ queries, which matches the best existing algorithms as well as the classical lower bound for sufficiently large $\epsilon$. Additionally, it can be readily adapted to a quantum query algorithm making $\tilde{O}(\epsilon^{-1}n^{4/3})$ queries, bypassing the classical lower bound. Complementary to these algorithmic results, we show a quantum lower bound of $\Omega(n)$ for $O(\Delta)$-coloring.

Related papers

• A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
  We present an algorithm that learns the edges of $G$ in at most $tildeO(d2m3/4)$ quantum queries. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in $tildeO(sqrtm)$ quantum queries.
  arXiv  Detail & Related papers  (2024-02-28T21:23:40Z)
• A faster and simpler algorithm for learning shallow networks [10.595936992218856]
  We revisit the well-studied problem of learning a linear combination of $k$ ReLU activations given labeled examples. Here we show that a simpler one-stage version of their algorithm suffices, and moreover its runtime is only $(d/varepsilon)O(k2)$.
  arXiv  Detail & Related papers  (2023-07-24T03:04:10Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  We show that an algorithm can obtain $O(log T)$ regret with just $O(sqrtT)$ hints under a natural query model. We also show that $o(sqrtT)$ hints cannot guarantee better than $Omega(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2021-11-09T16:50:18Z)
• Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
  Kawarabayashi and Thorup gave a near-trivial time deterministic algorithm for minimum cut in a simple graph $G = (V,E)$. We give a near-linear time randomized algorithm to find the $(1+varepsilon)$-KT partition of a weighted graph.
  arXiv  Detail & Related papers  (2021-11-02T05:26:10Z)
• A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs [1.0435741631709405]
  An $soperatorname-t$ minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects $s$ and $t$. In this work we describe a quantum algorithm for the minimum $soperatorname-t$ cut problem on undirected graphs.
  arXiv  Detail & Related papers  (2021-10-29T07:35:46Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
  A widely-used method to preserve the underlying hierarchical structure of the data is to find an embedding of the data into a tree or an ultrametric. In this paper, we provide a new algorithm which takes as input a set of points isometric in $mathbbRd2 (for universal constant $rho>1$) to output an ultrametric $Delta. We show that the output of our algorithm is comparable to the output of the linkage algorithms while achieving a much faster running time.
  arXiv  Detail & Related papers  (2020-08-15T11:06:45Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)

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.