Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOReach: Even Faster Reachability in Large Graphs
173
0
0.0
(
0
)
Added by
Kathrin Hanauer
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
One of the most fundamental problems in computer science is the reachability problem: Given a directed graph and two vertices s and t, can s reach t via a path? We revisit existing techniques and combine them with new approaches to support a large portion of reachability queries in constant time using a linear-sized reachability index. Our new algorithm OReach can be easily combined with previously developed solutions for the problem or run standalone. In a detailed experimental study, we compare a variety of algorithms with respect to their index-building and query times as well as their memory footprint on a diverse set of instances. Our experiments indicate that the query performance often depends strongly not only on the type of graph, but also on the result, i.e., reachable or unreachable. Furthermore, we show that previous algorithms are significantly sped up when combined with our new approach in almost all scenarios. Surprisingly, due to cache effects, a higher investment in space doesnt necessarily pay off: Reachability queries can often be answered even faster than single memory accesses in a precomputed full reachability matrix.
rate research
Read More
Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on $n$ vertices and a positive integer parameter $k$, find if there exist $k$ edges (arcs) whose deletion results in a graph that satisfies some specified parity constraints. In particular, when the objective is to obtain a connected graph in which all the vertices have even degrees---where the resulting graph is emph{Eulerian}---the problem is called Undirected Eulerian Edge Deletion. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion. Cygan et al. [emph{Algorithmica, 2014}] showed that these problems are fixed parameter tractable (FPT), and gave algorithms with the running time $2^{O(k log k)}n^{O(1)}$. They also asked, as an open problem, whether there exist FPT algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$. In this paper we answer their question in the affirmative: using the technique of computing emph{representative families of co-graphic matroids} we design algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$. The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. We believe that this view-point/approach will be useful in other problems where one of the constraints that need to be satisfied is that of connectivity.
We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on $H$-free graphs, that is, graphs that do not contain some fixed graph $H$ as an induced subgraph. In particular, we prove that both problems are polynomial-time solvable for $sP_3$-free graphs for every integer $sgeq 1$. Our results show that both problems exhibit the same behaviour on $H$-free graphs (subject to some open cases). This is in part explained by a new general algorithm we design for finding in a graph $G$ a largest induced subgraph whose blocks belong to some finite class ${cal C}$ of graphs. We also compare our results with the state-of-the-art results for the Odd Cycle Transversal problem, which is known to behave differently on $H$-free graphs.
In the sensitive distance oracle problem, there are three phases. We first preprocess a given directed graph $G$ with $n$ nodes and integer weights from $[-W,W]$. Second, given a single batch of $f$ edge insertions and deletions, we update the data structure. Third, given a query pair of nodes $(u,v)$, return the distance from $u$ to $v$. In the easier problem called sensitive reachability oracle problem, we only ask if there exists a directed path from $u$ to $v$. Our first result is a sensitive distance oracle with $tilde{O}(Wn^{omega+(3-omega)mu})$ preprocessing time, $tilde{O}(Wn^{2-mu}f^{2}+Wnf^{omega})$ update time, and $tilde{O}(Wn^{2-mu}f+Wnf^{2})$ query time where the parameter $muin[0,1]$ can be chosen. The data-structure requires $O(Wn^{2+mu} log n)$ bits of memory. This is the first algorithm that can handle $fgelog n$ updates. Previous results (e.g. [Demetrescu et al. SICOMP08; Bernstein and Karger SODA08 and FOCS09; Duan and Pettie SODA09; Grandoni and Williams FOCS12]) can handle at most 2 updates. When $3le flelog n$, the only non-trivial algorithm was by [Weimann and Yuster FOCS10]. When $W=tilde{O}(1)$, our algorithm simultaneously improves their preprocessing time, update time, and query time. In particular, when $f=omega(1)$, their update and query time is $Omega(n^{2-o(1)})$, while our update and query time are truly subquadratic in $n$, i.e., ours is faster by a polynomial factor of $n$. To highlight the technique, ours is the first graph algorithm that exploits the kernel basis decomposition of polynomial matrices by [Jeannerod and Villard J.Comp05; Zhou, Labahn and Storjohann J.Comp15] developed in the symbolic computation community. [...]
Motivated by recent Linear Programming solvers, we design dynamic data structures for maintaining the inverse of an $ntimes n$ real matrix under $textit{low-rank}$ updates, with polynomially faster amortized running time. Our data structure is based on a recursive application of the Woodbury-Morrison identity for implementing $textit{cascading}$ low-rank updates, combined with recent sketching technology. Our techniques and amortized analysis of multi-level partial updates, may be of broader interest to dynamic matrix problems. This data structure leads to the fastest known LP solver for general (dense) linear programs, improving the running time of the recent algorithms of (Cohen et al.19, Lee et al.19, Brand20) from $O^*(n^{2+ max{frac{1}{6}, omega-2, frac{1-alpha}{2}}})$ to $O^*(n^{2+max{frac{1}{18}, omega-2, frac{1-alpha}{2}}})$, where $omega$ and $alpha$ are the fast matrix multiplication exponent and its dual. Hence, under the common belief that $omega approx 2$ and $alpha approx 1$, our LP solver runs in $O^*(n^{2.055})$ time instead of $O^*(n^{2.16})$.
Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those measures is a major challenge in algorithmic network analysis. Aside from closeness and betweenness, Katz centrality is one of the established centrality measures. In this paper, we consider the problem of computing rankings for Katz centrality. In particular, we propose upper and lower bounds on the Katz score of a given node. While previous approaches relied on numerical approximation or heuristics to compute Katz centrality rankings, we construct an algorithm that iteratively improves those upper and lower bounds until a correct Katz ranking is obtained. We extend our algorithm to dynamic graphs while maintaining its correctness guarantees. Experiments demonstrate that our static graph algorithm outperforms both numerical approaches and heuristics with speedups between 1.5x and 3.5x, depending on the desired quality guarantees. Our dynamic graph algorithm improves upon the static algorithm for update batches of less than 10000 edges. We provide efficient parallel CPU and GPU implementations of our algorithms that enable near real-time Katz centrality computation for graphs with hundreds of millions of nodes in fractions of seconds.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
