Arrow Research search

Author name cluster

Sofya Vorotnikova

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.

2 papers
1 author row

Possible papers

2

SODA Conference 2020 Conference Paper

Vertex Ordering Problems in Directed Graph Streams

  • Amit Chakrabarti
  • Prantar Ghosh
  • Andrew McGregor 0001
  • Sofya Vorotnikova

We consider directed graph algorithms in a streaming setting, focusing on problems concerning orderings of the vertices. This includes such fundamental problems as topological sorting and acyclicity testing. We also study the related problems of finding a minimum feedback arc set (edges whose removal yields an acyclic graph), and finding a sink vertex. We are interested in both adversarially-ordered and randomly-ordered streams. For arbitrary input graphs with edges ordered adversarially, we show that most of these problems have high space complexity, precluding sublinear-space solutions. Some lower bounds also apply when the stream is randomly ordered: e. g. , in our most technical result we show that testing acyclicity in the p -pass random-order model requires roughly n 1+1/ p space. For other problems, random ordering can make a dramatic difference: e. g. , it is possible to find a sink in an acyclic tournament in the onepass random-order model using polylog( n ) space whereas under adversarial ordering roughly n 1/ p space is necessary and sufficient given Θ( p ) passes. We also design sublinear algorithms for the feedback arc set problem in tournament graphs; for random graphs; and for randomly ordered streams. In some cases, we give lower bounds establishing that our algorithms are essentially space-optimal. Together, our results complement the much maturer body of work on algorithms for undirected graph streams.

Details

SODA Conference 2016 Conference Paper

Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams

  • Rajesh Chitnis
  • Graham Cormode
  • Hossein Esfandiari
  • MohammadTaghi Hajiaghayi
  • Andrew McGregor 0001
  • Morteza Monemizadeh
  • Sofya Vorotnikova

In this paper we present a simple but powerful subgraph sampling primitive that is applicable in a variety of computational models including dynamic graph streams (where the input graph is defined by a sequence of edge/hyperedge insertions and deletions) and distributed systems such as MapReduce. In the case of dynamic graph streams, we use this primitive to prove the following results: Matching: Our main result for matchings is that there exists an Õ ( k 2 ) space algorithm that returns the edges of a maximum matching on the assumption the cardinality is at most k. The best previous algorithm used Õ ( kn ) space where n is the number of vertices in the graph and we prove our result is optimal up to logarithmic factors. Our algorithm has Õ (1) update time. We also show that there exists an Õ ( n 2 / α 3 ) space algorithm that returns an α -approximation for matchings of arbitrary size. In independent work, Assadi et al. (SODA 2016) proved this approximation algorithm is optimal and provided an alternative algorithm. We generalize our exact and approximate algorithms to weighted matching. For graphs with low arboricity such as planar graphs, the space required for constant approximation can be further reduced. While there has been a substantial amount of work on approximate matching in insert-only graph streams, these are the first nontrivial results in the dynamic setting. Vertex Cover and Hitting Set: There exists an Õ ( k d ) space algorithm that solves the minimum hitting set problem where d is the cardinality of the input sets and k is an upper bound on the size of the minimum hitting set. We prove this is optimal up to logarithmic factors. Our algorithm has Õ (1) update time. The case d = 2 corresponds to minimum vertex cover. Finally, we consider a larger family of parameterized problems (including b -matching, disjoint paths, vertex coloring among others) for which our subgraph sampling primitive yields fast, small-space dynamic graph stream algorithms. We then show lower bounds for natural problems outside this family.

Details