Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA quadratic algorithm for road coloring
371
0
0.0
(
0
)
Added by
Marie-Pierre B\\'eal
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The Road Coloring Theorem states that every aperiodic directed graph with constant out-degree has a synchronized coloring. This theorem had been conjectured during many years as the Road Coloring Problem before being settled by A. Trahtman. Trahtmans proof leads to an algorithm that finds a synchronized labeling with a cubic worst-case time complexity. We show a variant of his construction with a worst-case complexity which is quadratic in time and linear in space. We also extend the Road Coloring Theorem to the periodic case.
rate research
Read More
We consider a decentralized graph coloring model where each vertex only knows its own color and whether some neighbor has the same color as it. The networking community has studied this model extensively due to its applications to channel selection, rate adaptation, etc. Here, we analyze variants of a simple algorithm of Bhartia et al. [Proc., ACM MOBIHOC, 2016]. In particular, we introduce a variant which requires only $O(nlogDelta)$ expected recolorings that generalizes the coupon collector problem. Finally, we show that the $O(nDelta)$ bound Bhartia et al. achieve for their algorithm still holds and is tight in adversarial scenarios.
The graph isomorphism problem is of practical importance, as well as being a theoretical curiosity in computational complexity theory in that it is not known whether it is $NP$-complete or $P$. However, for many graphs, the problem is tractable, and related to the problem of finding the automorphism group of the graph. Perhaps the most well known state-of-the art implementation for finding the automorphism group is Nauty. However, Nauty is particularly susceptible to poor performance on star configurations, where the spokes of the star are isomorphic with each other. In this work, I present an algorithm that explodes these star configurations, reducing the problem to a sequence of simpler automorphism group calculations.
The matroid intersection problem is a fundamental problem that has been extensively studied for half a century. In the classic version of this problem, we are given two matroids $mathcal{M}_1 = (V, mathcal{I}_1)$ and $mathcal{M}_2 = (V, mathcal{I}_2)$ on a comment ground set $V$ of $n$ elements, and then we have to find the largest common independent set $S in mathcal{I}_1 cap mathcal{I}_2$ by making independence oracle queries of the form Is $S in mathcal{I}_1$? or Is $S in mathcal{I}_2$? for $S subseteq V$. The goal is to minimize the number of queries. Beating the existing $tilde O(n^2)$ bound, known as the quadratic barrier, is an open problem that captures the limits of techniques from two lines of work. The first one is the classic Cunninghams algorithm [SICOMP 1986], whose $tilde O(n^2)$-query implementations were shown by CLS+ [FOCS 2019] and Nguyen [2019]. The other one is the general cutting plane method of Lee, Sidford, and Wong [FOCS 2015]. The only progress towards breaking the quadratic barrier requires either approximation algorithms or a more powerful rank oracle query [CLS+ FOCS 2019]. No exact algorithm with $o(n^2)$ independence queries was known. In this work, we break the quadratic barrier with a randomized algorithm guaranteeing $tilde O(n^{9/5})$ independence queries with high probability, and a deterministic algorithm guaranteeing $tilde O(n^{11/6})$ independence queries. Our key insight is simple and fast algorithms to solve a graph reachability problem that arose in the standard augmenting path framework [Edmonds 1968]. Combining this with previous exact and approximation algorithms leads to our results.
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA19] states that in every $n$-vertex graph $G$ with maximum degree $Delta$, sampling $O(log{n})$ colors per each vertex independently from $Delta+1$ colors almost certainly allows for proper coloring of $G$ from the sampled colors. Besides being a combinatorial statement of its own independent interest, this theorem was shown to have various applications to design of algorithms for $(Delta+1)$ coloring in different models of computation on massive graphs such as streaming or sublinear-time algorithms. In this paper, we further study palette sparsification problems: * We prove that for $(1+varepsilon) Delta$ coloring, sampling only $O_{varepsilon}(sqrt{log{n}})$ colors per vertex is sufficient and necessary to obtain a proper coloring from the sampled colors. * A natural family of graphs with chromatic number much smaller than $(Delta+1)$ are triangle-free graphs which are $O(frac{Delta}{ln{Delta}})$ colorable. We prove that sampling $O(Delta^{gamma} + sqrt{log{n}})$ colors per vertex is sufficient and necessary to obtain a proper $O_{gamma}(frac{Delta}{ln{Delta}})$ coloring of triangle-free graphs. * We show that sampling $O_{varepsilon}(log{n})$ colors per vertex is sufficient for proper coloring of any graph with high probability whenever each vertex is sampling from a list of $(1+varepsilon) cdot deg(v)$ arbitrary colors, or even only $deg(v)+1$ colors when the lists are the sets ${1,ldots,deg(v)+1}$. Similar to previous work, our new palette sparsification results naturally lead to a host of new and/or improved algorithms for vertex coloring in different models including streaming and sublinear-time algorithms.
Massive sizes of real-world graphs, such as social networks and web graph, impose serious challenges to process and perform analytics on them. These issues can be resolved by working on a small summary of the graph instead . A summary is a compressed version of the graph that removes several details, yet preserves its essential structure. Generally, some predefined quality measure of the summary is optimized to bound the approximation error incurred by working on the summary instead of the whole graph. All known summarization algorithms are computationally prohibitive and do not scale to large graphs. In this paper we present an efficient randomized algorithm to compute graph summaries with the goal to minimize reconstruction error. We propose a novel weighted sampling scheme to sample vertices for merging that will result in the least reconstruction error. We provide analytical bounds on the running time of the algorithm and prove approximation guarantee for our score computation. Efficiency of our algorithm makes it scalable to very large graphs on which known algorithms cannot be applied. We test our algorithm on several real world graphs to empirically demonstrate the quality of summaries produced and compare to state of the art algorithms. We use the summaries to answer several structural queries about original graph and report their accuracies.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
