Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFully Dynamic Matching: Beating 2-Approximation in $Delta^epsilon$ Update Time
77
0
0.0
(
0
)
Added by
Soheil Behnezhad
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In fully dynamic graphs, we know how to maintain a 2-approximation of maximum matching extremely fast, that is, in polylogarithmic update time or better. In a sharp contrast and despite extensive studies, all known algorithms that maintain a $2-Omega(1)$ approximate matching are much slower. Understanding this gap and, in particular, determining the best possible update time for algorithms providing a better-than-2 approximate matching is a major open question. In this paper, we show that for any constant $epsilon > 0$, there is a randomized algorithm that with high probability maintains a $2-Omega(1)$ approximate maximum matching of a fully-dynamic general graph in worst-case update time $O(Delta^{epsilon}+text{polylog } n)$, where $Delta$ is the maximum degree. Previously, the fastest fully dynamic matching algorithm providing a better-than-2 approximation had $O(m^{1/4})$ update-time [Bernstein and Stein, SODA 2016]. A faster algorithm with update-time $O(n^epsilon)$ was known, but worked only for maintaining the size (and not the edges) of the matching in bipartite graphs [Bhattacharya, Henzinger, and Nanongkai, STOC 2016].
rate research
Read More
The problem of (vertex) $(Delta+1)$-coloring a graph of maximum degree $Delta$ has been extremely well-studied over the years in various settings and models. Surprisingly, for the dynamic setting, almost nothing was known until recently. In SODA18, Bhattacharya, Chakrabarty, Henzinger and Nanongkai devised a randomized data structure for maintaining a $(Delta+1)$-coloring with $O(log Delta)$ expected amortized update time. In this paper, we present a $(Delta+1)$-coloring data structure that achieves a constant amortized update time and show that this time bound holds not only in expectation but also with high probability.
We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph---which undergoes both edge insertions and deletions---in polylogarithmic time. Our algorithm is randomized and, per update, takes $O(log^2 Delta cdot log^2 n)$ expected time. Furthermore, the algorithm can be adjusted to have $O(log^2 Delta cdot log^4 n)$ worst-case update-time with high probability. Here, $n$ denotes the number of vertices and $Delta$ is the maximum degree in the graph. The MIS problem in fully dynamic graphs has attracted significant attention after a breakthrough result of Assadi, Onak, Schieber, and Solomon [STOC18] who presented an algorithm with $O(m^{3/4})$ update-time (and thus broke the natural $Omega(m)$ barrier) where $m$ denotes the number of edges in the graph. This result was improved in a series of subsequent papers, though, the update-time remained polynomial. In particular, the fastest algorithm prior to our work had $widetilde{O}(min{sqrt{n}, m^{1/3}})$ update-time [Assadi et al. SODA19]. Our algorithm maintains the lexicographically first MIS over a random order of the vertices. As a result, the same algorithm also maintains a 3-approximation of correlation clustering. We also show that a simpler variant of our algorithm can be used to maintain a random-order lexicographically first maximal matching in the same update-time.
Let $G=(V, E)$ be a given edge-weighted graph and let its {em realization} $mathcal{G}$ be a random subgraph of $G$ that includes each edge $e in E$ independently with probability $p$. In the {em stochastic matching} problem, the goal is to pick a sparse subgraph $Q$ of $G$ without knowing the realization $mathcal{G}$, such that the maximum weight matching among the realized edges of $Q$ (i.e. graph $Q cap mathcal{G}$) in expectation approximates the maximum weight matching of the whole realization $mathcal{G}$. In this paper, we prove that for any desirably small $epsilon in (0, 1)$, every graph $G$ has a subgraph $Q$ that guarantees a $(1-epsilon)$-approximation and has maximum degree only $O_{epsilon, p}(1)$. That is, the maximum degree of $Q$ depends only on $epsilon$ and $p$ (both of which are known to be necessary) and not for example on the number of nodes in $G$, the edge-weights, etc. The stochastic matching problem has been studied extensively on both weighted and unweighted graphs. Previously, only existence of (close to) half-approximate subgraphs was known for weighted graphs [Yamaguchi and Maehara, SODA18; Behnezhad et al., SODA19]. Our result substantially improves over these works, matches the state-of-the-art for unweighted graphs [Behnezhad et al., STOC20], and essentially settles the approximation factor.
The maximum matching problem in dynamic graphs subject to edge updates (insertions and deletions) has received much attention over the last few years; a multitude of approximation/time tradeoffs were obtained, improving upon the folklore algorithm, which maintains a maximal (and hence $2$-approximate) matching in $O(n)$ worst-case update time in $n$-node graphs. We present the first deterministic algorithm which outperforms the folklore algorithm in terms of {em both} approximation ratio and worst-case update time. Specifically, we give a $(2-Omega(1))$-approximate algorithm with $O(sqrt{n}sqrt[8]{m})=O(n^{3/4})$ worst-case update time in $n$-node, $m$-edge graphs. For sufficiently small constant $epsilon>0$, no deterministic $(2+epsilon)$-approximate algorithm with worst-case update time $O(n^{0.99})$ was known. Our second result is the first deterministic $(2+epsilon)$-approximate (weighted) matching algorithm with $O_epsilon(1)cdot O(sqrt[4]{m}) = O_epsilon(1)cdot O(sqrt{n})$ worst-case update time.
In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal $min(O(log n), f)$ approximation factor. (Throughout, $m$, $n$, $f$, and $C$ are parameters denoting the maximum number of sets, number of elements, frequency, and the cost range.) In the high-frequency range, when $f=Omega(log n)$, this was achieved by a deterministic $O(log n)$-approximation algorithm with $O(f log n)$ amortized update time [Gupta et al. STOC17]. In the low-frequency range, the line of work by Gupta et al. [STOC17], Abboud et al. [STOC19], and Bhattacharya et al. [ICALP15, IPCO17, FOCS19] led to a deterministic $(1+epsilon)f$-approximation algorithm with $O(f log (Cn)/epsilon^2)$ amortized update time. In this paper we improve the latter update time and provide the first bounds that subsume (and sometimes improve) the state-of-the-art dynamic vertex cover algorithms. We obtain: 1. $(1+epsilon)f$-approximation ratio in $O(flog^2 (Cn)/epsilon^3)$ worst-case update time: No non-trivial worst-case update time was previously known for dynamic set cover. Our bound subsumes and improves by a logarithmic factor the $O(log^3 n/text{poly}(epsilon))$ worst-case update time for unweighted dynamic vertex cover (i.e., when $f=2$ and $C=1$) by Bhattacharya et al. [SODA17]. 2. $(1+epsilon)f$-approximation ratio in $Oleft((f^2/epsilon^3)+(f/epsilon^2) log Cright)$ amortized update time: This result improves the previous $O(f log (Cn)/epsilon^2)$ update time bound for most values of $f$ in the low-frequency range, i.e. whenever $f=o(log n)$. It is the first that is independent of $m$ and $n$. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [SODA19] for unweighted dynamic vertex cover (i.e., when $f = 2$ and $C = 1$).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
