Digraph decompositions and monotonicity in digraph searching

Graph decompositions such as tree-decompositions and associated width measures have been the focus of much attention in structural and algorithmic graph theory. In particular, it has been found that many otherwise intractable problems become tractable on graph classes of bounded tree-width.More recently, proposals have been made to define a similar notion to tree-width for directed graphs. Several proposals have appeared so far, supported by algorithmic applications.In this paper we explore the limits of algorithmic applicability of digraph decompositions and show that various natural candidates for problems, which potentially could benefit from digraphs having small “directed width”, remain NP-complete even on almost acyclic graphs.Closely related to graph and digraph decompositions are graph searching games. An important property of graph searching games is monotonicity and a large number of papers addresses the question whether particular variants of these games are monotone. However, so far for two natural types of graph searching games-underlying DAG- and Kelly-decompositions-the question whether they are monotone was still open.We settle this issue by showing that both variants, the visible and the inert invisible graph searching games on directed graphs, are non-monotone.     

Time constrained graph searching

We consider time constraints for four models of searching graphs for intruders. One model is the standard cops and robber vertex-searching model with complete visibility. The second model differs from the preceding one only in that none of the searchers can see the intruder. The third model is a vertex-searching model in which searchers and an intruder move simultaneously and none of the searchers can see the intruder. The fourth model is simultaneous edge searching with an arbitrarily fast intruder.     

Monotonicity of non-deterministic graph searching

In graph searching, a team of searchers are aiming at capturing a fugitive moving in a graph. In the initial variant, called invisible graph searching, the searchers do not know the position of the fugitive until they catch it. In another variant, the searchers permanently know the position of the fugitive, i.e. the fugitive is visible. This latter variant is called visible graph searching. A search strategy that catches any fugitive in such a way that the part of the graph reachable by the fugitive never grows is called monotone. A priori, monotone strategies may require more searchers than general strategies to catch any fugitive. This is however not the case for visible and invisible graph searching. Two important consequences of the monotonicity of visible and invisible graph searching are: (1) the decision problem corresponding to the computation of the smallest number of searchers required to clear a graph is in NP, and (2) computing optimal search strategies is simplified by taking into account that there exist some that never backtrack.

Fomin et al. [F.V. Fomin, P. Fraigniaud, N. Nisse, Nondeterministic graph searching: From pathwidth to treewidth, in: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, MFCS’05, 2005, pp. 364–375] introduced an important graph searching variant, called non-deterministic graph searching, that unifies visible and invisible graph searching. In this variant, the fugitive is invisible, and the searchers can query an oracle that permanently knows the current position of the fugitive. The question of the monotonicity of non-deterministic graph searching was however left open.

In this paper, we prove that non-deterministic graph searching is monotone. In particular, this result is a unified proof of monotonicity for visible and invisible graph searching. As a consequence, the decision problem corresponding to non-deterministic graph searching belongs to NP. Moreover, the exact algorithms designed by Fomin et al. do compute optimal non-deterministic search strategies.     

Monotony properties of connected visible graph searching

Search games are attractive for their correspondence with classical width parameters. For instance, the invisible search number (a.k.a. node search number) of a graph is equal to its pathwidth plus 1, and the visible search number of a graph is equal to its treewidth plus 1. The connected variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on monotone search strategies, i.e., strategies for which every node is searched exactly once. The monotone connected visible search number of an n-node graph is at most O(logn) times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is Ω(logn). Second, we prove that, as opposed to the non-connected variant of visible graph searching, “recontamination helps” for connected visible search. Precisely, we prove that, for any k4, there exists a graph with connected visible search number at most k, and monotone connected visible search number >k     

Program graph allocation in distributed multicomputers

Data-flow multiprocessors have been shown to be a very efficient solution to the problem of multiprocessor schedulability. Recent research has demonstrated the critical importance of the proper allocation of program partitions to Processing Elements. We first describe in this paper several heuristic algorithms which have been used for program allocation. We then describe the layered approach to the problem of allocation (syntax directed and graph partitioning). A parallel approach to simulated annealing is used to perform allocation at the data-flow graph level. It is also shown how the results apply to the allocation problem in the Hughes Data-Flow Machine. Finally, simulation results indicate the validity of the solutions.     

An annotated bibliography on guaranteed graph searching

Graph searching encompasses a wide variety of combinatorial problems related to the problem of capturing a fugitive residing in a graph using the minimum number of searchers. In this annotated bibliography, we give an elementary classification of problems and results related to graph searching and provide a source of bibliographical references on this field.     

Combinatorial algorithms for distributed graph coloring

Numerous problems in Theoretical Computer Science can be solved very efficiently using powerful algebraic constructions. Computing shortest paths, constructing expanders, and proving the PCP Theorem, are just few examples of this phenomenon. The quest for combinatorial algorithms that do not use heavy algebraic machinery, but are roughly as efficient, has become a central field of study in this area. Combinatorial algorithms are often simpler than their algebraic counterparts. Moreover, in many cases, combinatorial algorithms and proofs provide additional understanding of studied problems. In this paper we initiate the study of combinatorial algorithms for Distributed Graph Coloring problems. In a distributed setting a communication network is modeled by a graph $G=(V,E)$ of maximum degree $\varDelta $ . The vertices of $G$ host the processors, and communication is performed over the edges of $G$ . The goal of distributed vertex coloring is to color $V$ with $(\varDelta + 1)$ colors such that any two neighbors are colored with distinct colors. Currently, efficient algorithms for vertex coloring that require $O(\varDelta + \log ^* n)$ time are based on the algebraic algorithm of Linial (SIAM J Comput 21(1):193–201, 1992) that employs set-systems. The best currently-known combinatorial set-system free algorithm, due to Goldberg et al. (SIAM J Discret Math 1(4):434–446, 1988), requires $O(\varDelta ^2+\log ^*n)$ time. We significantly improve over this by devising a combinatorial $(\varDelta + 1)$ -coloring algorithm that runs in $O(\varDelta + \log ^* n)$ time. This exactly matches the running time of the best-known algebraic algorithm. In addition, we devise a tradeoff for computing $O(\varDelta \cdot t)$ -coloring in $O(\varDelta /t + \log ^* n)$ time, for almost the entire range $1 < t < \varDelta $ . We also compute a Maximal Independent Set in $O(\varDelta + \log ^* n)$ time on general graphs, and in $O(\log n/ \log \log n)$ time on graphs of bounded arboricity. Prior to our work, these results could be only achieved using algebraic techniques. We believe that our algorithms are more suitable for real-life networks with limited resources, such as sensor networks.     

On the cost of searching signature trees

A precise analysis of the retrieval of signature trees is presented. A signature tree is a data structure constructed over a signature file to speed up searching all those signatures, which match a given query signature. The methods used include a detailed study of probabilistic analysis in conjunction with suitable contour integration of complex variabled functions.     

ViWoSG: A distributed scene graph of ultramassive distributed virtual environments

An ultra-massive distributed virtual environment generally consists of ultra-massive terrain data and a large quantity of objects and their attribute data, such as 2D/3D geometric models, audio/video, images, vectors, characteristics, etc. In this paper, we propose a novel method for constructing distributed scene graphs with high extensibility. Thismethod can support high concurrent interaction of clients and implement various tasks such as editing, querying, accessing and motion controlling. Some application experiments are performed to demonstrate its efficiency and soundness. Supported by the National Basic Research Program of China (Grant No. 2004CB719403), the National High-Tech Research & Development Program of China (Grant Nos. 2006AA01Z334, 2007AA01Z318, 2009AA01Z324), the National Natural Science Foundation of China (Grant Nos. 60573151, 60703062, 60833007), and the Marine 908-03-01-10 Project     

Efficiently searching a graph by a smell-oriented vertex process

Efficient graph search is a central issue in many aspects of AI. In most of existing work there is a distinction between the active “searcher”, which both executes the algorithm and holds the memory, and the passive “searched graph”, over which the searcher has no control at all. Large dynamic networks like the Internet, where the nodes are powerful computers and the links have narrow bandwidth and are heavily-loaded, call for a different paradigm, in which most of the burden of computing and memorizing is moved from the searching agent to the nodes of the network. In this paper we suggest a method for searching an undirected, connected graph using the Vertex-Ant-Walk method, where an a(ge)nt walks along the edges of a graph G, occasionally leaving “pheromone” traces at nodes, and using those traces to guide its exploration. We show that the ant can cover the graph within time O(nd), where n is the number of vertices and d the diameter of G. The use of traces achieves a trade-off between random and self-avoiding walks, as it dictates a lower priority for already-visited neighbors. Further properties of the suggested method are: (a) modularity: a group of searching agents, each applying the same protocol, can cooperate on a mission of covering a graph with minimal explicit communication between them; (b) possible convergence to a limit cycle: a Hamiltonian path in G (if one exists) is a possible limit cycle of the process. This revised version was published online in June 2006 with corrections to the Cover Date.     

The derivation of graph marking algorithms from distributed termination detection protocols

We show that on-the-fly garbage collection algorithms can be obtained by transforming distributed termination detection protocols. Virtually all known on-the-fly garbage collecting algorithms are obtained by applying the transformation. The approach leads to a novel and insightful derivation of, e.g., the concurrent garbage collection algorithms of Dijkstra et al. and of Hudak and Keller. The approach also leads to several new, highly parallel algorithms for concurrent garbage collection. We also analyze a garbage collecting system due to Hughes from our current perspective.     

Partitioning dynamic graph asynchronously with distributed FENNEL

Graph partitioning is important in distributed graph processing. Classical method such as METIS works well on relatively small graphs, but hard to scale for huge, dynamic graphs. Streaming graph partitioning algorithms overcome this issue by processing those graphs as streams. Among these algorithms, FENNEL achieves better edge cut ratio, even close to METIS, but consumes less memory and is significantly faster. On the other hand, graph partitioning may also benefit from distributed graph processing. However, to deploy FENNEL on a cluster, it is important to avoid quality loss and keep efficiency high. The direct implementation of this idea yields a synchronous model and a star-shaped network, which limits both scalability and efficiency. Targeting these two problems, we propose an asynchronous model, combined with a dedicated tree-shaped map-reduce network which is prevail in systems such as Apache Hadoop and Spark, to form AsyncFENNEL (asynchronous FENNEL). We theoretically prove that, the impact on partition quality brought by asynchronous model can be kept as minimal. We test AsyncFENNEL with various synthetic and real-world graphs, the comparison between synchronous and asynchronous models shows that, for streamed natural graphs, AsyncFENNEL can improve performance significantly (above 300% with 8 workers/partitions) with negligible loss on edge cut ratio. However, more worker nodes will introduce a heavier network traffic and reduce efficiency. The proposed tree-shaped map-reduce network can mitigate that impact and increase the performance in that case.     

An efficient distributed algorithm for detection of knots and cycles in a distributed graph

Knot detection in a distributed graph is an important problem and finds applications in deadlock detection in several areas such as store-and-forward networks, distributed simulation, and distributed database systems. This paper presents an efficient distributed algorithm to detect if a node is part of a knot in a distributed graph. The algorithm requires 2e messages and a delay of 2(d+1) message hops to detect if a node in a distributed graph is in a knot (here, e is the number of edges in the reachable part of the distributed graph and d is its diameter). A significant advantage of this algorithm is that it not only detects if a node is involved in a knot, but also finds exactly which nodes are involved in the knot. Moreover, if the node is not involved in a knot, but is only involved in a cycle, then it finds the nodes that are in a cycle with that node. We illustrate the working of the algorithm with examples. The paper ends with a discussion on how the information about the nodes involved in the knot can be used for deadlock resolution and also on the performance of the algorithm.     

分布式多线程并行处理技术在大规模化学结构检索数据库系统中的应用

提出以分布式、多线程并行处理技术实现基于甲骨文数据库管理系统的高效大规模化学结构检索数据库系统的方法;以相同的结构搜索算法和不同的模块组合机制分别构建了单机单线程、单机多线程、分布式单线程和分布式多线程4种不同的化学结构检索数据库系统,并在4种不同的实现方案下对同一组化学结构分别做了结构检索实验。结果表明：在4种实现方案中,分布式多线程并行处理方法的检索效率最高,稳定性也很好(与其他3种实现方法相同)。该方法已成功应用于微芯公司开发的TASS(Target Activityand Structure System)软件系统中。     

A distributed approach for graph mining in massive networks

We propose a novel distributed algorithm for mining frequent subgraphs from a single, very large, labeled network. Our approach is the first distributed method to mine a massive input graph that is too large to fit in the memory of any individual compute node. The input graph thus has to be partitioned among the nodes, which can lead to potential false negatives. Furthermore, for scalable performance it is crucial to minimize the communication among the compute nodes. Our algorithm, DistGraph, ensures that there are no false negatives, and uses a set of optimizations and efficient collective communication operations to minimize information exchange. To our knowledge DistGraph is the first approach demonstrated to scale to graphs with over a billion vertices and edges. Scalability results on up to 2048 IBM Blue Gene/Q compute nodes, with 16 cores each, show very good speedup.     

Tuning the granularity of parallelism for distributed graph processing

Popular distributed graph processing frameworks, such as Pregel and GraphLab, are based on the vertex-centric computation model, where users write their customized Compute function for each vertex to process the data iteratively. Vertices are evenly partitioned among the compute nodes, and the granularity of parallelism of the graph algorithm is normally tuned by adjusting the number of compute nodes. Vertex-centric model splits the computation into phases. Inside one specific phase, the computation proceeds as an embarrassingly parallel process, because no communication between compute nodes incurs. By default, current graph engine only handles one iteration of the algorithm in a phase. However, in this paper, we find that we can also tune the granularity of parallelism, by aggregating the computation of multiple iterations into one phase, which has a significant impact on the performance of the graph algorithm. In the ideal case, if all computations are handled in one phase, the whole algorithm turns into an embarrassingly parallel algorithm and the benefit of parallelism is maximized. Based on this observation, we propose two approaches, a function-based approach and a parameter-based approach, to automatically transform a Pregel algorithm into a new one with tunable granularity of parallelism. We study the cost of such transformation and the trade-off between the granularity of parallelism and the performance. We provide a new direction to tune the performance of parallel algorithms. Finally, the approaches are implemented in our graph processing system, N2, and we illustrate their performance using popular graph algorithms.