Arrow Research search

Author name cluster

Shay Solomon

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

28 papers
1 author row

Possible papers

28

FOCS Conference 2024 Conference Paper

A Lossless Deamortization for Dynamic Greedy Set Cover

  • Shay Solomon
  • Amitai Uzrad
  • Tianyi Zhang 0008

The dynamic set cover problem has been subject to growing research attention in recent years. In this problem, we are given as input a dynamic universe of at most $n$ elements and a fixed collection of $m$ sets, where each element appears in a most $f$ sets and the cost of each set is in [1/C, 1], and the goal is to efficiently maintain an approximate minimum set cover under element updates. Two algorithms that dynamize the classic greedy algorithm are known, providing $O(\log n)$ and $((1+\epsilon)\ln n)$ -approximation with amortized update times $O(f \log n)$ and, $O(\frac{f \log n}{\epsilon})$, respectively [GKKP (STOC'17); SU (STOC'23)]. The question of whether one can get approximation $O(\log n)$ (or even worse) with low worst-case update time has remained open — only the naive $O(f\cdot n)$ time bound is known, even for unweighted instances. In this work we devise the first amortized greedy algorithm that is amenable to an efficient deamortization, and also develop a lossless deamortization approach suitable for the set cover problem, the combination of which yields a $((1+\epsilon)\ln n){-}$ approximation algorithm with a worst-case update time of $O(\frac{f \log n}{\epsilon^{2}})$. Our worst-case time bound — the first to break the naive $O(f\cdot n)$ bound — matches the previous best amortized bound, and actually improves its $\epsilon$ -dependence. Further, to demonstrate the applicability of our deamortization approach, we employ it, in conjunction with the primal-dual amortized algorithm of [BHN (FOCS'19)], to obtain a $((1+\epsilon)f)$ -approximation algorithm with a worst-case update time of $O(\frac{f \log n}{\epsilon^{2}})$, improving over the previous best bound of $O(\frac{f \cdot \log ^{2}(C n)}{-3})\ [$ BHNW (SODA'21)]. Finally, as direct implications of our results for set cover, we (i) achieve the first nontrivial worst-case update time for the dominating set problem, and (ii) improve the state-of-the-art worst-case update time for the vertex cover problem.

Details

FOCS Conference 2024 Conference Paper

Faster (Δ+1)-Edge Coloring: Breaking the m√n Time Barrier

  • Sayan Bhattacharya
  • Din Carmon
  • Martín Costa
  • Shay Solomon
  • Tianyi Zhang 0008

Vizing's theorem states that any n-vertex m-edge graph of maximum degree $\Delta$ can be edge colored using at most $\Delta+1$ different colors [Diskret. Analiz, '64]. Vizing's original proof is algorithmic and shows that such an edge coloring can be found in $\tilde{O}(mn)$ time. This was subsequently improved to $\tilde{O}(m\sqrt{n})$, independently by Arjomandi [1982] and by Gabow et al. [1985]. In this paper we present an algorithm that computes such an edge coloring in $\tilde{O}(mn^{1/3})$, time, giving the first polynomial improvement for this fundamental problem in over 40 years.

Details

SODA Conference 2024 Conference Paper

Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time

  • Sayan Bhattacharya
  • Martín Costa
  • Nadav Panski
  • Shay Solomon

We consider the problem of maintaining a (1 + ɛ )∆-edge coloring in a dynamic graph G with n nodes and maximum degree at most Δ. The state-of-the-art update time is O ɛ (polylog( n )), by Duan, He and Zhang [SODA’19] and by Christiansen [STOC’23], and more precisely O (log 7 n / ɛ 2 ), where Δ = Ω(log 2 n / ɛ 2 ). The following natural question arises: What is the best possible update time of an algorithm for this task? More specifically, can we bring it all the way down to some constant (for constant ɛ )? This question coincides with the static time barrier for the problem: Even for (2Δ — 1)-coloring, there is only a naive O(m log Δ)-time algorithm. We answer this fundamental question in the affirmative, by presenting a dynamic (1 + ɛ )Δ-edge coloring algorithm with O (log 4 (1/ ɛ )/ ɛ 9 ) update time, provided Δ = Ω ɛ (polylog( n )). As a corollary, we also get the first linear time (for constant ɛ ) static algorithm for (1 + ɛ )Δ-edge coloring; in particular, we achieve a running time of O(m log(1/ ɛ )/ ɛ 2 ). We obtain our results by carefully combining a variant of the N ibble algorithm from Bhattacharya, Grandoni and Wajc [SODA’21] with the subsampling technique of Kulkarni, Liu, Sah, Sawhney and Tarnawski [STOC’22].

Details

FOCS Conference 2024 Conference Paper

Towards Instance-Optimal Euclidean Spanners

  • Hung Le 0001
  • Shay Solomon
  • Cuong Than
  • Csaba D. Tóth
  • Tianyi Zhang 0008

Euclidean spanners are important geometric objects that have been extensively studied since the 1980s. The two most basic “compactness” measures of a Euclidean spanner $E$ 1 2 We shall identify a graph $H = (X, E)$ with its edge set $E$. All edge weights are given by the Euclidean distances. are the size (number of edges) $\vert E\vert$ and the weight (sum of edge weights) $\Vert E\Vert$. The state-of-the-art constructions of Euclidean $(1+\epsilon)$ -spanners in $\mathbb{R}^{d}$ have $o_{d}(_{n\cdot\epsilon^{-d+1}})$ edges (or sparsity $O_{d}(\epsilon^{-d+1}))$ and weight $O_{d}(\epsilon^{-d} \log \epsilon^{-1}) \cdot\Vert E_{\text{mst}}\Vert$ (or lightness $O_{d}(\epsilon^{-d}\log\epsilon^{-1}))$; here $O_{d}$ suppresses a factor of $d^{O(d)}$ and $\Vert E_{\text{mst}}\Vert$ denotes the weight of a minimum spanning tree of the input point set. Importantly, these two upper bounds are (near-)optimal (up to the $d^{O(d)}$ factor and disregarding the factor of $\log(\epsilon^{-1})$ in the lightness bound) for some extremal instances [Le and Solomon, 2019], and therefore they are (near-)optimal in an existential sense. Moreover, both these upper bounds are attained by the same construction-the classic greedy spanner, whose sparsity and lightness are not only existentially optimal, but they also significantly outperform those of any other Euclidean spanner construction studied in an experimental study by [Farshi-Gudmundsson, 2009] for various practical point sets in the plane. This raises the natural question of whether the greedy spanner is (near-) optimal for any point set instance? Motivated by this question, we initiate the study of instance optimal Euclidean spanners. Our results are two-fold. •Rather surprisingly (given the aforementioned experimental study), we demonstrate that the greedy spanner is far from being instance optimal, even when allowing its stretch to grow. More concretely, we design two hard instances of point sets in the plane, where the greedy $(1+x\epsilon)$ -spanner (for basically any parameter $x \geq 1$ ) has $\Omega_{x}(\epsilon^{-1/2})\cdot\vert E_{\text{spa}} \vert$ edges and weight $\Omega_{x}(\epsilon^{-1})\cdot\Vert E_{\text{light}}\Vert$, where $E_{\text{spa}}$ and $E_{\text{light}}$ denote the per-instance sparsest and lightest $(1 +\epsilon)$ -spanners, respectively, and the $\Omega_{x}$ notation suppresses a polynomial dependence on $1/x$. •As our main contribution, we design a new construction of Euclidean spanners, which is inherently different from known constructions, achieving the following bounds: a stretch of $1+\epsilon\cdot 2^{O(\log^{*}(d/\epsilon)}$ with $O(1)\cdot\vert E_{\text{spa}}\vert$ edges and weight $O(1)$. $\Vert E_{ \text{light}}\Vert$. In other words, we show that a slight increase to the stretch suffices for obtaining instance optimality up to an absolute constant for both sparsity and lightness. Remarkably, there is only a log-star dependence on the dimension in the stretch, and there is no dependence on it whatsoever in the number of edges and weight. In general, for any integer $k\geq 1$, we can construct a Euclidean spanner in $\mathbb{R}^{d}$ of stretch $1+\epsilon\cdot 2^{O(k)}$ with $O(\log^{(k)}(\epsilon^{-1})+\log^{(k-1)}(d))\cdot\vert E_{\text{spa}}\vert$ edges and weight $O(\log^{(k)}(\epsilon^{-1})+\log^{(k-1)}(d))\cdot\Vert E_{\text{light}}\Vert$, where $\log^{(k)}$ denotes the k-iterated logarithm.

Details

STOC Conference 2023 Conference Paper

A Unified Framework for Light Spanners

  • Hung Le 0001
  • Shay Solomon

Seminal works on light spanners over the years provide spanners with optimal lightness in various graph classes, such as in general graphs, Euclidean spanners, and minor-free graphs. Three shortcomings of previous works on light spanners are: (i) The runtimes of these constructions are almost always sub-optimal, and usually far from optimal. (ii) These constructions are optimal in the standard and crude sense, but not in a refined sense that takes into account a wider range of involved parameters. (iii) The techniques are ad hoc per graph class, and thus can’t be applied broadly. This work aims at addressing these shortcomings by presenting a unified framework of light spanners in a variety of graph classes. Informally, the framework boils down to a transformation from sparse spanners to light spanners; since the state-of-the-art for sparse spanners is much more advanced than that for light spanners, such a transformation is powerful. First, we apply our framework to design fast constructions with optimal lightness for several graph classes. Second, we apply our framework to achieve more refined optimality bounds for several graph classes, i.e., the bounds remain optimal when taking into account a wider range of involved parameters, most notably є. Our new constructions are significantly better than the state-of-the-art for every examined graph class.

Details

FOCS Conference 2023 Conference Paper

Covering Planar Metrics (and Beyond): O(1) Trees Suffice

  • Hsien-Chih Chang
  • Jonathan Conroy
  • Hung Le 0001
  • Lazar Milenkovic
  • Shay Solomon
  • Cuong Than

While research on the geometry of planar graphs has been active in the past decades, many properties of planar metrics remain mysterious. This paper studies a fundamental aspect of the planar graph geometry: covering planar metrics by a small collection of simpler metrics. Specifically, a tree cover of a metric space $(X, \delta)$ is a collection of trees, so that every pair of points u and v in X has a low-distortion path in at least one of the trees. The celebrated “Dumbbell Theorem” [ADM + 95] states that any low-dimensional Euclidean space admits a tree cover with $O(1)$ trees and distortion $1+\varepsilon$, for any fixed $\varepsilon \in(0, 1)$. This result has found numerous algorithmic applications, and has been generalized to the wider family of doubling metrics [BFN19]. Does the same result hold for planar metrics? A positive answer would add another evidence to the well-observed connection between Euclidean/doubling metrics and planar metrics. In this work, we answer this fundamental question affirmatively. Specifically, we show that for any given fixed $\varepsilon \in(0, 1)$, any planar metric can be covered by $O(1)$ trees with distortion $1+\varepsilon$. Our result for planar metrics follows from a rather general framework: First we reduce the problem to constructing tree covers with additive distortion. Then we introduce the notion of shortcut partition, and draw connection between shortcut partition and additive tree cover. Finally we prove the existence of shortcut partition for any planar metric, using new insights regarding the grid-like structure of planar graphs. To demonstrate the power of our framework: •We establish additional tree cover results beyond planar metrics; in particular, we present an $O(1)$-size tree cover with distortion $1+\varepsilon$ for bounded treewidth metrics; •We obtain several algorithmic applications in planar graphs from our tree cover. The grid-like structure is a technical contribution that we believe is of independent interest. We showcase its applicability beyond tree cover by constructing a simpler and better embedding of planar graphs into $O(1)$-treewidth graphs with small additive distortion, resolving an open problem in this line of research.

Details

STOC Conference 2023 Conference Paper

Dynamic ((1+ε) ln n)-Approximation Algorithms for Minimum Set Cover and Dominating Set

  • Shay Solomon
  • Amitai Uzrad

The minimum set cover (MSC) problem admits two classic algorithms: a greedy ln n -approximation and a primal-dual f -approximation, where n is the universe size and f is the maximum frequency of an element. Both algorithms are simple and efficient, and remarkably — one cannot improve these approximations under hardness results by more than a factor of (1+є), for any constant є > 0. In their pioneering work, Gupta et al. [STOC’17] showed that the greedy algorithm can be dynamized to achieve O (log n )-approximation with update time O ( f log n ). Building on this result, Hjuler et al. [STACS’18] dynamized the greedy minimum dominating set (MDS) algorithm, achieving a similar approximation with update time O (Δ log n ) (the analog of O ( f log n )), albeit for unweighted instances. The approximations of both algorithms, which are the state-of-the-art, exceed the static ln n -approximation by a rather large constant factor. In sharp contrast, the current best dynamic primal-dual MSC algorithms, by Bhattacharya et al. [SODA’21] and Assadi-Solomon [ESA’21], both with update time O ( f 2 ) — exceed the static f -approximation by a factor of (at most) 1+є, for any є > 0. This paper aims to bridge the gap between the best approximation factor of the dynamic greedy MSC and MDS algorithms and the static ln n bound. We present dynamic algorithms for weighted greedy MSC and MDS with approximation (1+є)ln n for any є > 0, while achieving the same update time (ignoring dependencies on є) of the best previous algorithms (with approximation significantly larger than ln n ). Moreover, we prove that the same algorithms achieve O (min{ log n , log C }) amortized recourse ; the recourse measures the number of changes to the maintained structure per update step, and the cost of each set lies in the range [1/ C ,1].

Details

FOCS Conference 2023 Conference Paper

Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier

  • Hung Le 0001
  • Shay Solomon
  • Cuong Than

An essential requirement of spanners in many applications is to be fault-tolerant: a $(1+\epsilon)$-spanner of a metric space is called (vertex) f-fault-tolerant $(f-F T)$ if it remains a $(1+\epsilon)$-spanner (for the non-faulty points) when up to f faulty points are removed from the spanner. Fault-tolerant (FT) spanners for Euclidean and doubling metrics have been extensively studied since the 90 s. For low-dimensional Euclidean metrics, Czumaj and Zhao in SoCG’03 [CZ03] showed that the optimal guarantees $O(f n), O(f)$ and $O\left(f^{2}\right)$ on the size, degree and lightness of f-FT spanners can be achieved via a greedy algorithm, which naïvely runs in $O\left(n^{3}\right) \cdot 2^{O(f)}$ time. $^{1}$ An earlier construction, by Levcopoulos et al. [LNS98] from STOC’98, has a faster running time of $O(n \log n)+n 2^{O(f)}$, but has a slack of $2^{\Omega(f)}$ in all the three involved parameters. The question of whether the optimal bounds of [CZ03] can be achieved via a fast construction has remained elusive, with the lightness parameter being the bottleneck: Any construction (other than [CZ03]) has lightness either $2^{\Omega(f)}$ or $\Omega(\log n)$. Moreover, in the wider family of doubling metrics, it is not even clear whether there exists an f FT spanner with lightness that depends solely on f (even exponentially): all existing constructions have lightness $\Omega(\log n)$ since they are built on the net-tree spanner, which is induced by a hierarchical net-tree of lightness $\Omega(\log n)$. In this paper we settle in the affirmative these longstanding open questions. Specifically, we design a construction of f-FT spanners that is optimal with respect to all the involved parameters (size, degree, lightness and running time): For any n-point doubling metric, any $\epsilon\gt0$, and any integer $1 \le \log f n\le + {nfn}-)$, an2, our construction provides, -spanner with within time $O(n$ size $O (fn)$, degree $O(f)$ and lightness $O(f^{2})$. To break the $\Omega (\log n)$ lightness barrier, we introduce a new geometric object — the light net-forest. Like the net-tree, the light net-forest is induced by a hierarchy of nets. However, to ensure small lightness, the light net-forest is inherently less “well-connected” than the net-tree, which, in turn, makes the task of achieving fault-tolerance significantly more challenging. Further, to achieve the optimal degree (and size) together with optimal lightness, and to do so within the optimal running time — we overcome several highly nontrivial technical challenges.

Details

SODA Conference 2022 Conference Paper

Near-Optimal Spanners for General Graphs in (Nearly) Linear Time

  • Hung Le 0001
  • Shay Solomon

Let G = ( V, E, w ) be a weighted undirected graph on | V| = n vertices and | E| = m edges, let k ≥ 1 be any integer, and let ∊ < 1 be any parameter. We present the following results on fast constructions of spanners with near-optimal sparsity and lightness, 1 which culminate a long line of work in this area. (By near-optimal we mean optimal under Erdos' girth conjecture and disregarding the ∊ -dependencies.) There are (deterministic) algorithms for constructing (2 k –1)(1 + ∊ )-spanners for G with a near-optimal sparsity of O ( n 1/ k · log(1/ ∊ )/ ∊ )). The first algorithm can be implemented in the pointer-machine model within time O(mα(m, n ) · log(1/ ∊ )/ ∊ )+ SORT( m )), where α (·, ·) is the two-parameter inverse-Ackermann function and SORT( m ) is the time needed to sort m integers. The second algorithm can be implemented in the Word RAM model within time O ( m log(1/ ∊ )/ ∊ )). There is a (deterministic) algorithm for constructing a (2 k –1)(1 + ∊ )-spanner for G that achieves a near-optimal bound of O(n 1/ k ·poly(1/ ∊ )) on both sparsity and lightness. This algorithm can be implemented in the pointer-machine model within time O ( m α( m, n ) · poly(1/ ∊ ) + SORT( m )) and in the Word RAM model within time O(mα(m, n ) · poly(1/ ∊ )). The previous fastest constructions of (2 k –1)(1 + ∊ )-spanners with near-optimal sparsity incur a runtime of is O (min{ m(n 1+1/k ) + n log n, k · n 2+1/ k }), even regardless of the lightness. Importantly, the greedy spanner for stretch 2 k –1 has sparsity O ( n 1/ k ) — with no ∊ -dependence whatsoever, but its runtime is O(m ( n 1+1/ k + n log n )). Moreover, the state-of-the-art lightness bound of any (2 k –1)-spanner (including the greedy spanner) is poor, even regardless of the sparsity and runtime.

Details

SODA Conference 2019 Conference Paper

(1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time

  • Fabrizio Grandoni 0001
  • Stefano Leonardi 0001
  • Piotr Sankowski
  • Chris Schwiegelshohn
  • Shay Solomon

We study the matching problem in the incremental setting, where we are given a sequence of edge insertions and aim at maintaining a near-maximum cardinality matching of the graph with small update time. We present a deterministic algorithm that, for any constant ε > 0, maintains a (1 + ε )-approximate matching with constant amortized update time per insertion.

Details

SODA Conference 2019 Conference Paper

Fully Dynamic Maximal Independent Set with Sublinear in n Update Time

  • Sepehr Assadi
  • Krzysztof Onak
  • Baruch Schieber
  • Shay Solomon

The first fully dynamic algorithm for maintaining a maximal independent set (MIS) with update time that is sublinear in the number of edges was presented recently by the authors of this paper [Assadi et al. , STOC’18]. The algorithm is deterministic and its update time is O ( m 3/4 ), where m is the (dynamically changing) number of edges. Subsequently, Gupta and Khan and independently Du and Zhang [arXiv, April 2018] presented deterministic algorithms for dynamic MIS with update times of O ( m 2/3 ) and O ( m 2/3 ), respectively. Du and Zhang also gave a randomized algorithm with update time. Moreover, they provided some partial (conditional) hardness results hinting that the update time of m 1/2– ε, and in particular n 1– ε for n -vertex dense graphs, is a natural barrier for this problem for any constant ε > 0, for deterministic and randomized algorithms that satisfy a certain natural property. In this paper, we break this natural barrier and present the first fully dynamic (randomized) algorithm for maintaining an MIS with update time that is always sublinear in the number of vertices, namely, an expected amortized update. We also show that a simpler variant of our algorithm can already achieve an Õ ( m 1/3 ) expected amortized update time, which results in an improved performance over our update time algorithm for sufficiently sparse graphs, and breaks the m 1/2 barrier of Du and Zhang for all values of m.

Details

FOCS Conference 2019 Conference Paper

Truly Optimal Euclidean Spanners

  • Hung Le 0001
  • Shay Solomon

Euclidean spanners are important geometric structures, having found numerous applications over the years. Cornerstone results in this area from the late 80s and early 90s state that for any d-dimensional n-point Euclidean space, there exists a (1+ε) -spanner with O(nε^-d+1) edges and lightness (normalized weight) O(ε^-2d)^1. Surprisingly, the fundamental question of whether or not these dependencies on ε and d for small d can be improved has remained elusive, even for d = 2. This question naturally arises in any application of Euclidean spanners where precision is a necessity (thus ε is tiny). In the most extreme case ε is inverse polynomial in n, and then one could potentially improve the size and lightness bounds by factors that are polynomial in n. The state-of-the-art bounds O(nε^-d+1) and O(ε^-2d) on the size and lightness of spanners are realized by the greedy spanner. In 2016, Filtser and Solomon [25] proved that, in low dimensional spaces, the greedy spanner is “near-optimal''; informally, their result states that the greedy spanner for dimension d is just as sparse and light as any other spanner but for dimension larger by a constant factor. Hence the question of whether the greedy spanner is truly optimal remained open to date. The contribution of this paper is two-fold. 1) We resolve these longstanding questions by nailing down the exact dependencies on ε and d and showing that the greedy spanner is truly optimal. Specifically, for any d= O(1), ε = Ω(n^-1/d-1): • We show that any (1+ε) -spanner must have Ω(nε^-d+1) edges, implying that the greedy (and other) spanners achieve the optimal size. • We show that any (1+ε) -spanner must have lightness Ω(ε^-d), and then improve the upper bound on the lightness of the greedy spanner from O(ε^-2d) to Õ_ε (ε^-d). 2) We then complement our negative result for the size of spanners with a rather counterintuitive positive result: Steiner points lead to a quadratic improvement in the size of spanners! Our bound for the size of Steiner spanners is tight as well (up to lower-order terms).

Details

STOC Conference 2018 Conference Paper

Fully dynamic maximal independent set with sublinear update time

  • Sepehr Assadi
  • Krzysztof Onak
  • Baruch Schieber
  • Shay Solomon

A maximal independent set (MIS) can be maintained in an evolving m -edge graph by simply recomputing it from scratch in O ( m ) time after each update. But can it be maintained in time sublinear in m in fully dynamic graphs? We answer this fundamental open question in the affirmative. We present a deterministic algorithm with amortized update time O (min{Δ, m 3/4 }), where Δ is a fixed bound on the maximum degree in the graph and m is the (dynamically changing) number of edges. We further present a distributed implementation of our algorithm with O (min{Δ, m 3/4 }) amortized message complexity, and O (1) amortized round complexity and adjustment complexity (the number of vertices that change their output after each update). This strengthens a similar result by Censor-Hillel, Haramaty, and Karnin (PODC’16) that required an assumption of a non-adaptive oblivious adversary.

Details

SODA Conference 2016 Conference Paper

Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach

  • David Peleg
  • Shay Solomon

Approximate matchings in fully dynamic graphs have been intensively studied in recent years. Gupta and Peng [FOCS'13] presented a deterministic algorithm for maintaining fully dynamic (1 + ∊)-approximate maximum cardinality matching (MCM) in general graphs with worst-case update time, for any ∊ > 0, where m denotes the current number of edges in the graph. Despite significant research efforts, this update time barrier remains the state-of-the-art even if amortized time bounds and randomization are allowed or the approximation factor is allowed to increase from 1 + ∊ to 2 – ∊, and even in basic graph families such as planar graphs. This paper presents a simple deterministic algorithm whose performance depends on the density of the graph. Specifically, we maintain fully dynamic (1 + ∊)-approximate MCM with worst-case update time O ( α · ∊ –2 ) for graphs with arboricity 1 bounded by α. The update time bound holds even if the arboricity bound α changes dynamically. Since the arboricity ranges between 1 and, our density-sensitive bound O ( α ·∊ –2 ) naturally generalizes the bound of Gupta and Peng. For the family of bounded arboricity graphs (which includes forests, planar graphs, and graphs excluding a fixed minor), in the regime ∊ = O (1) our update time reduces to a constant. This should be contrasted with the previous best 2-approximation results for bounded arboricity graphs, which achieve either an O (log n ) worst-case bound (Kopelowitz et al, ICALP'14) or an amortized bound (He et al. , ISAAC'14), where n stands for the number of vertices in the graph. En route to this result, we provide local algorithms of independent interest for maintaining fully dynamic approximate matching and vertex cover.

Details

FOCS Conference 2016 Conference Paper

Fully Dynamic Maximal Matching in Constant Update Time

  • Shay Solomon

Baswana, Gupta and Sen [FOCS'11] showed that fully dynamic maximal matching can be maintained in general graphs with logarithmic amortized update time. More specifically, starting from an empty graph on n fixed vertices, they devised a randomized algorithm for maintaining maximal matching over any sequence of t edge insertions and deletions with a total runtime of O(t log n) in expectation and O(t log n + n log 2 n) with high probability. Whether or not this runtime bound can be improved towards O(t) has remained an important open problem. Despite significant research efforts, this question has resisted numerous attempts at resolution even for basic graph families such as forests. In this paper, we resolve the question in the affirmative, by presenting a randomized algorithm for maintaining maximal matching in general graphs with constant amortized update time. The optimal runtime bound O(t) of our algorithm holds both in expectation and with high probability. As an immediate corollary, we can maintain 2-approximate vertex cover with constant amortized update time. This result is essentially the best one can hope for (under the unique games conjecture) in the context of dynamic approximate vertex cover, culminating a long line of research. Our algorithm builds on Baswana et al. 's algorithm, but is inherently different and arguably simpler. As an implication of our simplified approach, the space usage of our algorithm is linear in the (dynamic) graph size, while the space usage of Baswana et al. 's algorithm is always at least Ω(n log n). Finally, we present applications to approximate weighted matchings and to distributed networks.

Details

SODA Conference 2016 Conference Paper

Local-on-Average Distributed Tasks

  • Merav Parter
  • David Peleg
  • Shay Solomon

A distributed task is local if its time complexity is (nearly) constant, otherwise it is global. Unfortunately, local tasks are relatively scarce, and most distributed tasks require time at least logarithmic in the network size (and often higher than that). In a dynamic setting, i. e. , when the network undergoes repeated and frequent topological changes, such as vertex and edge insertions and deletions, it is desirable to be able to perform a local update procedure around the modified part of the network, rather than running a static global algorithm from scratch following each change. This paper makes a step towards establishing the hypothesis that many (statically) non-local distributed tasks are local-on-average in the dynamic setting, namely, their amortized time complexity is O (log* n ). Towards establishing the plausibility of this hypothesis, we propose a strategy for transforming static O (polylog( n )) time algorithms into dynamic O (log* n ) amortized time update procedures. We then demonstrate the usefulness of our strategy by applying it to several fundamental problems whose static time complexity is logarithmic, including forest-decomposition, edge-orientation and coloring sparse graphs, and show that their amortized time complexity in the dynamic setting is indeed O (log* n ).

Details

STOC Conference 2014 Conference Paper

From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics

  • Shay Solomon

A (1+ ε )- spanner for a doubling metric ( X, δ ) is a subgraph H of the complete graph corresponding to ( X, δ ), which preserves all pairwise distances to within a factor of 1 + ε . A natural requirement from a spanner, which is essential for many applications (mainly in distributed systems or wireless networks), is to be robust against vertex and edge failures -- so that even when some vertices and edges in the network fail, we still have a (1 + ε )-spanner for what remains. The spanner H is called a k-fault-tolerant (1 + ε )- spanner , for 1 ≤ k ≤ n -- 2, if for any F ⊆ X with | F | ≤ k , the graph H -- F (obtained by removing from H the vertices of F and their incident edges) is a (1 + ε )-spanner for X -- F .

Details

SODA Conference 2013 Conference Paper

Fast Constructions of Light-Weight Spanners for General Graphs

  • Michael Elkin
  • Shay Solomon

Since the pioneering works of Peleg and Schäffer [32], Althöfer et al. [4], and Chandra et al. [13], it is known that for every weighted undirected n -vertex m -edge graph G = ( V, E ), and every integer k ≥ 1, there exists a ((2 k − 1) • (1 + ∊))-spanner with O ( n 1+1/ k ) edges and weight O ( k · n 1/ k ) · ω( MST ( G )), for an arbitrarily small constant ∊ > 0. (Here ω( M ST ( G )) stands for the weight of the minimum spanning tree of G.) Nearly linear time algorithms for constructing (2 k − 1)-spanners with nearly O ( n 1+1/ k ) edges were devised in [11, 38, 37]. However, these algorithms fail to guarantee any meaningful upper bound on the weight of the constructed spanners. To our knowledge, there are only two known algorithms for constructing sparse and light spanners for general graphs. One of them is the greedy algorithm of Althöfer et al. [4], analyzed by Chandra et al. [13]. The drawback of the greedy algorithm is that it requires O ( m · ( n 1+1 / + n · log n )) time. The other algorithm is due to Awerbuch et al. [7], from 1991. It constructs O ( k )-spanners with O ( k · n 1+1/ k · λ) edges, weight O ( k 2 · n 1/ k · λ ) · ω( MST ( G )), within time O ( m · k · n 1/ k · λ ), where λ is the logarithm of the aspect ratio of the graph. The running time of both these algorithms is unsatisfactory. Moreover, the usually faster algorithm of [7] pays for the speedup by significantly increasing both the stretch, the sparsity, and the weight of the resulting spanner. In this paper we devise an efficient algorithm for constructing sparse and light spanners. Specifically, our algorithm constructs ((2 k − 1) · (1 + ∊))-spanners with O ( k · n 1+1/ k ) edges and weight O ( k · n 1/ k ) · ω( MST ( G )), where ∊ > 0 is an arbitrarily small constant. The running time of our algorithm is O ( k · m + min{ n · log n, m · α( n )}). Moreover, by slightly increasing the running time we can reduce the other parameters. These results address an open problem from the ESA'04 paper by Roditty and Zwick [38].

Details

STOC Conference 2013 Conference Paper

Optimal euclidean spanners: really short, thin and lanky

  • Michael Elkin
  • Shay Solomon

The degree, the (hop-)diameter, and the weight are the most basic and well-studied parameters of geometric spanners. In a seminal STOC'95 paper, titled "Euclidean spanners: short, thin and lanky", Arya et al. [2] devised a construction of Euclidean (1+ε)-spanners that achieves constant degree, diameter O(log n), weight O(log 2 n) ⋅ ω(MST), and has running time O(n ⋅ log n). This construction applies to n-point constant-dimensional Euclidean spaces. Moreover, Arya et al. conjectured that the weight bound can be improved by a logarithmic factor, without increasing the degree and the diameter of the spanner, and within the same running time. This conjecture of Arya et al. became one of the most central open problems in the area of Euclidean spanners. Nevertheless, the only progress since 1995 towards its resolution was achieved in the lower bounds front: Any spanner with diameter O(log n) must incur weight Ω(log n) ⋅ ω(MST), and this lower bound holds regardless of the stretch or the degree of the spanner [12, 1]. In this paper we resolve the long-standing conjecture of Arya et al. in the affirmative. We present a spanner construction with the same stretch, degree, diameter, and running time, as in Arya et al.'s result, but with optimal weight O(log n) ⋅ ω(MST). So our spanners are as thin and lanky as those of Arya et al., but they are really short! Moreover, our result is more general in three ways. First, we demonstrate that the conjecture holds true not only in constant-dimensional Euclidean spaces, but also in doubling metrics . Second, we provide a general tradeoff between the three involved parameters, which is tight in the entire range . Third, we devise a transformation that decreases the lightness of spanners in general metrics , while keeping all their other parameters in check. Our main result is obtained as a corollary of this transformation.

Details

FOCS Conference 2011 Conference Paper

Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones

  • Michael Elkin
  • Shay Solomon

For a pair of parameters α, β ≥ 1, a spanning tree T of a weighted undirected n-vertex graph G = (V, E, w) is called an (α, β)-shallow-light tree (shortly, (α, β-SLT) of G with respect to a designated vertex rt ∈ V if (1) it approximates all distances from rt to the other vertices up to a factor of α, and (2) its weight is at most β times the weight of the minimum spanning tree MST(G) of G. The parameter α (respectively, β) is called the root-distortion (resp. , lightness) of the tree T. Shallow-light trees (SLTs) constitute a fundamental graph structure, with numerous theoretical and practical applications. In particular, they were used for constructing spanners, in network design, for VLSI-circuit design, for various data gathering and dissemination tasks in wireless and sensor networks, in overlay networks, and in the message-passing model of distributed computing. Tight tradeoffs between the parameters of SLTs were established by Awer buch et al. [5], [6] and Khuller et al. [33]. They showed that for any ϵ >; 0 there always exist (1+ϵ, O(1/ϵ))-SLTs, and that the upper bound β = O(1/ϵ) on the lightness of SLTs cannot be improved. In this paper we show that using Steiner points one can build SLTs with logarithmic lightness, i. e. , β = O(log 1/ϵ). This establishes an exponential separation between spanning SLTs and Steiner ones. One particularly remarkable point on our tradeoff curve is ϵ = 0. In this regime our construction provides a shortest-path tree with weight at most O(log n) · w(MST(G)). Moreover, we prove matching lower bounds that show that all our results are tight up to constant factors. Finally, on our way to these results we settle (up to constant factors) a number of open questions that were raised by Khuller et al. [33] in SODA'93.

Details

FOCS Conference 2008 Conference Paper

Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners

  • Yefim Dinitz
  • Michael Elkin
  • Shay Solomon

We show that for every n-point metric space M and positive integer k, there exists a spanning tree T with unweighted diameter O(k) and weight w(T) = O(k ldr n 1/k ) ldr w(MST(M)), and a spanning tree T' with weight w(T') = O(k) ldr w(MST(M)) and unweighted diameter O(k ldr n 1/k ). Moreover, there is a designated point rt such that for every other point v, both dist T (rt, v) and dist T (rt, v) are at most (1 + epsiv) ldr dist M (rt, v), for an arbitrarily small constant epsiv > 0. We prove that the above tradeoffs are tight up to constant factors in the entire range of parameters. Furthermore, our lower bounds apply to a basic one-dimensional Euclidean space. Finally, our lower bounds for the particular case of unweighted diameter O(log n) settle a long-standing open problem in Computational Geometry.

Details
v2026.09.13