This work begins a systematic study of basic problems in directed \emph{acyclic} graphs (DAGs) and shows that reachability from a single vertex and even topological sorting are both computable in O(n \log^3 n) many cut queries.
Abstract
In the cut-query model, an algorithm is given access to a graph $G = (V, E)$ \emph{only} via cut queries. This model has seen significant attention in the undirected graph setting, with works establishing $O(n)$ cut query algorithms for computing the global minimum cut, $\widetilde{O}(n^{3/2})$ cut query algorithms for all pairs minimum cut, and many more. However, despite this vast array of progress in designing sub-quadratic query algorithms for computing properties of undirected graphs, there has been \emph{no} progress in designing such algorithms in directed graphs. Indeed, even for basic problems like whether a vertex $t$ is reachable from a vertex $s$, the cut query complexity is only known to be bounded in the interval $[\Omega(n), O(n^2 / \log n)]$. In this work, we begin a systematic study of these basic problems in directed \emph{acyclic} graphs (DAGs). In this setting, we show that reachability from a single vertex and even topological sorting are both computable in $O(n \log^3 n)$ many cut queries. As a consequence, we also obtain an algorithm which, for any \emph{arbitrary} directed graph $G$, uses only $O(n \log^3 n)$ cut queries and determines whether $G$ contains a cycle.
This work restricts its attention to directed acyclic graphs (DAGs) and obtains a deterministic single-source reachability algorithm using $O(n \sqrt{n \log n})$ queries, based on a topological sort algorithm, and can also be adapted to compute single-source shortest paths in DAGs.
B. Bals, Matei Tinca, Yasamin Nazari· arXiv.org· 0 citations
Consider a poset - or equivalently an $n$-vertex DAG $G=(V, E)$ - and a boolean function $f: V \rightarrow \{0, 1\}$ on its vertex set. We say $f$ is monotone if $f(u) \leq f(v)$ for all $(u, v) \in E$. While there is extensive literature on the query complexity of testing monotonicity, we focus instead on the space complexity and initiate the study of this problem in the streaming setting. Namely, the edges of $G$ arrive in an arbitrary order, and the goal is to estimate distance to monotonicity of a given function $f$ using $\widetilde{O}(n)$ space. Note that while this space allows receiving and storing $f$, it is much smaller than the input graph $G$ which could have up to $\Omega(n^2)$ edges. Our main result is an algorithm that $(1+\epsilon)$-approximates distance to monotonicity in $\sqrt{n}^{1+o(1)}$ passes. We also prove that this is the best pass-complexity one can hope for, for any $O(1)$-approximation, short of improving the state-of-the-art streaming algorithm for $st$-reachability, which is a very well-studied problem. On the technical side, our algorithm approximates the size of maximum matching in (a subgraph of) the transitive closure of $G$. While the maximum matching problem has received significant attention in the streaming setting, the fact that we are computing it in the transitive closure requires very different ideas. In fact, a main contribution of our work is to connect sublinear time algorithms for estimating the maximum matching size to the streaming setting for the first time. While existing off-the-shelf sublinear time algorithms only result in an $n\sqrt{n}^{1+o(1)}$ pass algorithm in our setting, we show how to significantly improve upon them by allowing stronger queries (such as vertex and subset queries) that can be implemented just as efficiently as more standard adjacency matrix and list queries for our problem.
Amir Azarmehr, Soheil Behnezhad, Lily Chung et al.· 0 citations
This paper provides the first truly linear-time approximation scheme for the Densest Subgraph Problem, and uses assignments arising from a flow-based formulation together with a structural carving lemma to progressively carve "sparse" parts of the graph while nearly preserving the densest subgraph.
This work shows that one can maintain an O(\alpha)-approximate MDS with update time for dynamic graphs whose {\em arboricity} is bounded by $\alpha$ throughout the update sequence, which replaces the dependence on $\Delta$ in prior update bounds with $\alpha$, while also improving the approximation guarantee for bounded-arboricity graphs.
A. Bukov, Shay Solomon· Embedded Systems and Applica...· 0 citations
In the three-terminal Reachability-Preserving Minimum Edge Cut problem, the input is an undirected edge-weighted graph with terminals \(s_1,s_2,t\). The objective is to delete a minimum-cost set of edges that separates \(t\) from both \(s_1\) and \(s_2\), while preserving connectivity between \(s_1\) and \(s_2\). We give a polynomial-time \(O(\log n)\)-approximation algorithm. The algorithm uses a probabilistic distribution of cut-dominating decomposition trees. A direct transfer of a connected tree solution to the original graph is not valid because a connected tree cluster may induce a disconnected vertex set in the graph. We overcome this obstruction by expanding every rooted tree cluster into the connected components it induces in the original graph. These components form a node-weighted auxiliary graph. A minimum node-weighted path in this auxiliary graph produces a connected feasible source side. The main structural observation is that the total graph-boundary cost of all connected components of a rooted tree cluster is no greater than the capacity of the corresponding tree edge. This permits the auxiliary path to be compared with a tree cut separating an optimal preserved \(s_1\)-\(s_2\) path from \(t\). Combining this comparison with the expected \(O(\log n)\) cut distortion of the decomposition trees proves the approximation guarantee.
It is shown that bidirectional Dijkstra is still instance-optimal on simple undirected weighted graphs under the order-oblivious model, where incident edges are given in a random order, and under the order-dependent model, where bidirectional Dijkstra is not instance-optimal.
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
