ﻻ يوجد ملخص باللغة العربية
In this paper we introduce a notion of spectral approximation for directed graphs. While there are many potential ways one might define approximation for directed graphs, most of them are too strong to allow sparse approximations in general. In contrast, we prove that for our notion of approximation, such sparsifiers do exist, and we show how to compute them in almost linear time. Using this notion of approximation, we provide a general framework for solving asymmetric linear systems that is broadly inspired by the work of [Peng-Spielman, STOC`14]. Applying this framework in conjunction with our sparsification algorithm, we obtain an almost linear time algorithm for solving directed Laplacian systems associated with Eulerian Graphs. Using this solver in the recent framework of [Cohen-Kelner-Peebles-Peng-Sidford-Vladu, FOCS`16], we obtain almost linear time algorithms for solving a directed Laplacian linear system, computing the stationary distribution of a Markov chain, computing expected commute times in a directed graph, and more. For each of these problems, our algorithms improves the previous best running times of $O((nm^{3/4} + n^{2/3} m) log^{O(1)} (n kappa epsilon^{-1}))$ to $O((m + n2^{O(sqrt{log{n}loglog{n}})}) log^{O(1)} (n kappa epsilon^{-1}))$ where $n$ is the number of vertices in the graph, $m$ is the number of edges, $kappa$ is a natural condition number associated with the problem, and $epsilon$ is the desired accuracy. We hope these results open the door for further studies into directed spectral graph theory, and will serve as a stepping stone for designing a new generation of fast algorithms for directed graphs.
The girth of a graph, i.e. the length of its shortest cycle, is a fundamental graph parameter. Unfortunately all known algorithms for computing, even approximately, the girth and girth-related structures in directed weighted $m$-edge and $n$-node gra
Let $G$ be a graph and $S, T subseteq V(G)$ be (possibly overlapping) sets of terminals, $|S|=|T|=k$. We are interested in computing a vertex sparsifier for terminal cuts in $G$, i.e., a graph $H$ on a smallest possible number of vertices, where $S c
We study the algorithmic properties of the graph class Chordal-ke, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. We discover that a number of fundamental
In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph $D$ on $n$ vertices and $m$ edges, and an integer $k$. The objective is to determine whether there exists a set of at most $k$ vertices intersecting every directed cycl
We give almost-linear-time algorithms for constructing sparsifiers with $n poly(log n)$ edges that approximately preserve weighted $(ell^{2}_2 + ell^{p}_p)$ flow or voltage objectives on graphs. For flow objectives, this is the first sparsifier const