The problem of sparsifying a graph or a hypergraph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Benczur and Karger (1996) showed that given any $n$-vertex undirected weigh
ted graph $G$ and a parameter $varepsilon in (0,1)$, there is a near-linear time algorithm that outputs a weighted subgraph $G$ of $G$ of size $tilde{O}(n/varepsilon^2)$ such that the weight of every cut in $G$ is preserved to within a $(1 pm varepsilon)$-factor in $G$. The graph $G$ is referred to as a {em $(1 pm varepsilon)$-approximate cut sparsifier} of $G$. Subsequent recent work has obtained a similar result for the more general problem of hypergraph cut sparsifiers. However, all known sparsification algorithms require $Omega(n + m)$ time where $n$ denotes the number of vertices and $m$ denotes the number of hyperedges in the hypergraph. Since $m$ can be exponentially large in $n$, a natural question is if it is possible to create a hypergraph cut sparsifier in time polynomial in $n$, {em independent of the number of edges}. We resolve this question in the affirmative, giving the first sublinear time algorithm for this problem, given appropriate query access to the hypergraph.
Cuts in graphs are a fundamental object of study, and play a central role in the study of graph algorithms. The problem of sparsifying a graph while approximately preserving its cut structure has been extensively studied and has many applications. In
a seminal work, Benczur and Karger (1996) showed that given any $n$-vertex undirected weighted graph $G$ and a parameter $varepsilon in (0,1)$, there is a near-linear time algorithm that outputs a weighted subgraph $G$ of $G$ of size $tilde{O}(n/varepsilon^2)$ such that the weight of every cut in $G$ is preserved to within a $(1 pm varepsilon)$-factor in $G$. The graph $G$ is referred to as a {em $(1 pm varepsilon)$-approximate cut sparsifier} of $G$. A natural question is if such cut-preserving sparsifiers also exist for hypergraphs. Kogan and Krauthgamer (2015) initiated a study of this question and showed that given any weighted hypergraph $H$ where the cardinality of each hyperedge is bounded by $r$, there is a polynomial-time algorithm to find a $(1 pm varepsilon)$-approximate cut sparsifier of $H$ of size $tilde{O}(frac{nr}{varepsilon^2})$. Since $r$ can be as large as $n$, in general, this gives a hypergraph cut sparsifier of size $tilde{O}(n^2/varepsilon^2)$, which is a factor $n$ larger than the Benczur-Karger bound for graphs. It has been an open question whether or not Benczur-Karger bound is achievable on hypergraphs. In this work, we resolve this question in the affirmative by giving a new polynomial-time algorithm for creating hypergraph sparsifiers of size $tilde{O}(n/varepsilon^2)$.
We study the problem of finding a spanning forest in an undirected, $n$-vertex multi-graph under two basic query models. One is the Linear query model which are linear measurements on the incidence vector induced by the edges; the other is the weaker
OR query model which only reveals whether a given subset of plausible edges is empty or not. At the heart of our study lies a fundamental problem which we call the {em single element recovery} problem: given a non-negative real vector $x$ in $N$ dimension, return a single element $x_j > 0$ from the support. Queries can be made in rounds, and our goals is to understand the trade-offs between the query complexity and the rounds of adaptivity needed to solve these problems, for both deterministic and randomized algorithms. These questions have connections and ramifications to multiple areas such as sketching, streaming, graph reconstruction, and compressed sensing. Our main results are: * For the single element recovery problem, it is easy to obtain a deterministic, $r$-round algorithm which makes $(N^{1/r}-1)$-queries per-round. We prove that this is tight: any $r$-round deterministic algorithm must make $geq (N^{1/r} - 1)$ linear queries in some round. In contrast, a $1$-round $O(log^2 N)$-query randomized algorithm which succeeds 99% of the time is known to exist. * We design a deterministic $O(r)$-round, $tilde{O}(n^{1+1/r})$-OR query algorithm for graph connectivity. We complement this with an $tilde{Omega}(n^{1 + 1/r})$-lower bound for any $r$-round deterministic algorithm in the OR-model. * We design a randomized, $2$-round algorithm for the graph connectivity problem which makes $tilde{O}(n)$-OR queries. In contrast, we prove that any $1$-round algorithm (possibly randomized) requires $tilde{Omega}(n^2)$-OR queries.
We give the first polynomial-time approximation scheme (PTAS) for the stochastic load balancing problem when the job sizes follow Poisson distributions. This improves upon the 2-approximation algorithm due to Goel and Indyk (FOCS99). Moreover, our ap
proximation scheme is an efficient PTAS that has a running time double exponential in $1/epsilon$ but nearly-linear in $n$, where $n$ is the number of jobs and $epsilon$ is the target error. Previously, a PTAS (not efficient) was only known for jobs that obey exponential distributions (Goel and Indyk, FOCS99). Our algorithm relies on several probabilistic ingredients including some (seemingly) new results on scaling and the so-called focusing effect of maximum of Poisson random variables which might be of independent interest.
We consider the problem of designing sublinear time algorithms for estimating the cost of a minimum metric traveling salesman (TSP) tour. Specifically, given access to a $n times n$ distance matrix $D$ that specifies pairwise distances between $n$ po
ints, the goal is to estimate the TSP cost by performing only sublinear (in the size of $D$) queries. For the closely related problem of estimating the weight of a metric minimum spanning tree (MST), it is known that for any $varepsilon > 0$, there exists an $tilde{O}(n/varepsilon^{O(1)})$ time algorithm that returns a $(1 + varepsilon)$-approximate estimate of the MST cost. This result immediately implies an $tilde{O}(n/varepsilon^{O(1)})$ time algorithm to estimate the TSP cost to within a $(2 + varepsilon)$ factor for any $varepsilon > 0$. However, no $o(n^2)$ time algorithms are known to approximate metric TSP to a factor that is strictly better than $2$. On the other hand, there were also no known barriers that rule out the existence of $(1 + varepsilon)$-approximate estimation algorithms for metric TSP with $tilde{O}(n)$ time for any fixed $varepsilon > 0$. In this paper, we make progress on both algorithms and lower bounds for estimating metric TSP cost. We also show that the problem of estimating metric TSP cost is closely connected to the problem of estimating the size of a maximum matching in a graph.
Suppose a graph $G$ is stochastically created by uniformly sampling vertices along a line segment and connecting each pair of vertices with a probability that is a known decreasing function of their distance. We ask if it is possible to reconstruct t
he actual positions of the vertices in $G$ by only observing the generated unlabeled graph. We study this question for two natural edge probability functions -- one where the probability of an edge decays exponentially with the distance and another where this probability decays only linearly. We initiate our study with the weaker goal of recovering only the order in which vertices appear on the line segment. For a segment of length $n$ and a precision parameter $delta$, we show that for both exponential and linear decay edge probability functions, there is an efficient algorithm that correctly recovers (up to reflection symmetry) the order of all vertices that are at least $delta$ apart, using only $tilde{O}(frac{n}{delta ^ 2})$ samples (vertices). Building on this result, we then show that $O(frac{n^2 log n}{delta ^2})$ vertices (samples) are sufficient to additionally recover the location of each vertex on the line to within a precision of $delta$. We complement this result with an $Omega (frac{n^{1.5}}{delta})$ lower bound on samples needed for reconstructing positions (even by a computationally unbounded algorithm), showing that the task of recovering positions is information-theoretically harder than recovering the order. We give experimental results showing that our algorithm recovers the positions of almost all points with high accuracy.
We study the vertex-decremental Single-Source Shortest Paths (SSSP) problem: given an undirected graph $G=(V,E)$ with lengths $ell(e)geq 1$ on its edges and a source vertex $s$, we need to support (approximate) shortest-path queries in $G$, as $G$ un
dergoes vertex deletions. In a shortest-path query, given a vertex $v$, we need to return a path connecting $s$ to $v$, whose length is at most $(1+epsilon)$ times the length of the shortest such path, where $epsilon$ is a given accuracy parameter. The problem has many applications, for example to flow and cut problems in vertex-capacitated graphs. Our main result is a randomized algorithm for vertex-decremental SSSP with total expected update time $O(n^{2+o(1)}log L)$, that responds to each shortest-path query in $O(nlog L)$ time in expectation, returning a $(1+epsilon)$-approximate shortest path. The algorithm works against an adaptive adversary. The main technical ingredient of our algorithm is an $tilde O(|E(G)|+ n^{1+o(1)})$-time algorithm to compute a emph{core decomposition} of a given dense graph $G$, which allows us to compute short paths between pairs of query vertices in $G$ efficiently. We believe that this core decomposition algorithm may be of independent interest. We use our result for vertex-decremental SSSP to obtain $(1+epsilon)$-approximation algorithms for maximum $s$-$t$ flow and minimum $s$-$t$ cut in vertex-capacitated graphs, in expected time $n^{2+o(1)}$, and an $O(log^4n)$-approximation algorithm for the vertex version of the sparsest cut problem with expected running time $n^{2+o(1)}$. These results improve upon the previous best known results for these problems in the regime where $m= omega(n^{1.5 + o(1)})$.
We present new lower bounds that show that a polynomial number of passes are necessary for solving some fundamental graph problems in the streaming model of computation. For instance, we show that any streaming algorithm that finds a weighted minimum
$s$-$t$ cut in an $n$-vertex undirected graph requires $n^{2-o(1)}$ space unless it makes $n^{Omega(1)}$ passes over the stream. To prove our lower bounds, we introduce and analyze a new four-player communication problem that we refer to as the hidden-pointer chasing problem. This is a problem in spirit of the standard pointer chasing problem with the key difference that the pointers in this problem are hidden to players and finding each one of them requires solving another communication problem, namely the set intersection problem. Our lower bounds for graph problems are then obtained by reductions from the hidden-pointer chasing problem. Our hidden-pointer chasing problem appears flexible enough to find other applications and is therefore interesting in its own right. To showcase this, we further present an interesting application of this problem beyond streaming algorithms. Using a reduction from hidden-pointer chasing, we prove that any algorithm for submodular function minimization needs to make $n^{2-o(1)}$ value queries to the function unless it has a polynomial degree of adaptivity.
In the subgraph counting problem, we are given a input graph $G(V, E)$ and a target graph $H$; the goal is to estimate the number of occurrences of $H$ in $G$. Our focus here is on designing sublinear-time algorithms for approximately counting occurr
ences of $H$ in $G$ in the setting where the algorithm is given query access to $G$. This problem has been studied in several recent papers which primarily focused on specific families of graphs $H$ such as triangles, cliques, and stars. However, not much is known about approximate counting of arbitrary graphs $H$. This is in sharp contrast to the closely related subgraph enumeration problem that has received significant attention in the database community as the database join problem. The AGM bound shows that the maximum number of occurrences of any arbitrary subgraph $H$ in a graph $G$ with $m$ edges is $O(m^{rho(H)})$, where $rho(H)$ is the fractional edge-cover of $H$, and enumeration algorithms with matching runtime are known for any $H$. We bridge this gap between subgraph counting and subgraph enumeration by designing a sublinear-time algorithm that can estimate the number of any arbitrary subgraph $H$ in $G$, denoted by $#H$, to within a $(1pm epsilon)$-approximation w.h.p. in $O(frac{m^{rho(H)}}{#H}) cdot poly(log{n},1/epsilon)$ time. Our algorithm is allowed the standard set of queries for general graphs, namely degree queries, pair queries and neighbor queries, plus an additional edge-sample query that returns an edge chosen uniformly at random. The performance of our algorithm matches those of Eden et.al. [FOCS 2015, STOC 2018] for counting triangles and cliques and extend them to all choices of subgraph $H$ under the additional assumption of edge-sample queries. We further show that our algorithm works for the more general database join size estimation problem and prove a matching lower bound for this problem.
In the submodular cover problem, we are given a non-negative monotone submodular function $f$ over a ground set $E$ of items, and the goal is to choose a smallest subset $S subseteq E$ such that $f(S) = Q$ where $Q = f(E)$. In the stochastic version
of the problem, we are given $m$ stochastic items which are different random variables that independently realize to some item in $E$, and the goal is to find a smallest set of stochastic items whose realization $R$ satisfies $f(R) = Q$. The problem captures as a special case the stochastic set cover problem and more generally, stochastic covering integer programs. We define an $r$-round adaptive algorithm to be an algorithm that chooses a permutation of all available items in each round $k in [r]$, and a threshold $tau_k$, and realizes items in the order specified by the permutation until the function value is at least $tau_k$. The permutation for each round $k$ is chosen adaptively based on the realization in the previous rounds, but the ordering inside each round remains fixed regardless of the realizations seen inside the round. Our main result is that for any integer $r$, there exists a poly-time $r$-round adaptive algorithm for stochastic submodular cover whose expected cost is $tilde{O}(Q^{{1}/{r}})$ times the expected cost of a fully adaptive algorithm. Prior to our work, such a result was not known even for the case of $r=1$ and when $f$ is the coverage function. On the other hand, we show that for any $r$, there exist instances of the stochastic submodular cover problem where no $r$-round adaptive algorithm can achieve better than $Omega(Q^{{1}/{r}})$ approximation to the expected cost of a fully adaptive algorithm. Our lower bound result holds even for coverage function and for algorithms with unbounded computational power.
