Parameterized algorithms for feedback set problems and their duals in tournaments

The parameterized feedback vertex (arc) set problem is to find whether there are k vertices (arcs) in a given graph whose removal makes the graph acyclic. The parameterized complexity of this problem in general directed graphs is a long standing open problem. We investigate the problems on tournaments, a well studied class of directed graphs. We consider both weighted and unweighted versions.     

On the hardness of finding near-optimal multicuts in directed acyclic graphs

Given an edge-weighted (di)graph and a list of source-sink pairs of vertices of this graph, the minimum multicut problem consists in selecting a minimum-weight set of edges (or arcs), whose removal leaves no path from each source to the corresponding sink. This is a well-known NP-hard problem, and improving several previous results, we show that it remains APX-hard in unweighted directed acyclic graphs (DAG), even with only two source-sink pairs. This is also true if we remove vertices instead of arcs.     

On a game in directed graphs

Inspired by recent algorithms for electing a leader in a distributed system, we study the following game in a directed graph: each vertex selects one of its outgoing arcs (if any) and eliminates the other endpoint of this arc; the remaining vertices play on until no arcs remain. We call a directed graph lethal if the game must end with all vertices eliminated and mortal if it is possible that the game ends with all vertices eliminated. We show that lethal graphs are precisely collections of vertex-disjoint cycles, and that the problem of deciding whether or not a given directed graph is mortal is NP-complete (and hence it is likely that no “nice” characterization of mortal graphs exists).     

Average-Case Analysis of Greedy Packet Scheduling

Abstract. We study the average number of delays suffered by packets routed using greedy (work conserving) scheduling policies. We obtain tight bounds on the worst-case average number of delays in a few cases as follows. First, we show that the worst-case average number of delays is a function of the number of sources of packets, which is interesting in case a node may send many packets. Then, using a new concept we call delay race , we prove a tight bound on the average number of delays in a leveled graph. Finally, using delay races in a more involved way, we prove nearly tight bounds on the average number of delays in directed acyclic graphs (DAGs). The upper bound for DAGs is expressed in terms of the underlying topology, and as a result it holds for any acyclic set of routes, even if they are not shortest paths. The lower bound for DAGs, on the other hand, holds even for shortest paths routes.     

Privacy-preserving authentication of trees and graphs

Secure data sharing in third-party environments such as the cloud requires that both authenticity and confidentiality of the data be assured, especially when such structures encode sensitive information (such as in XML documents). Existing authentication schemes for trees and directed acyclic graphs (DAGs) are authenticity-preserving, but not confidentiality-preserving, and lead to leakage of sensitive information during authentication. In this paper, we propose a family of three leakage-free authentication schemes for (1) tree data structures, (2) directed acyclic graphs (DAGs), and (3) graphs (with cycles), which are also efficient. This family of schemes referred to as the “structural signatures” is based on the structure of the tree as defined by tree traversals and aggregate signatures. We also show through complexity and performance analysis that our scheme is practical in terms of the cost for authentication of data. We have also discussed two applications of the proposed scheme: (1) automatic correction and recovery from structural errors, and (2) secure publish /subscribe of XML documents.     

有向无环图的高效归约算法

将一个应用程序部署到给定的片上网络上执行时,需要将应用程序中的每一个子任务都指派给片上网络中的一个节点执行。该问题一般被建模成一组子任务作为顶点的有向无环图,任务在片上网络上的部署过程就等同于一个有向无环图的顶点向一个片上网络拓扑映射的过程。而随着应用程序和片上网络规模的增大,计算一个最优的映射方案是典型的难解问题。为了加速有向无环图到片上网络拓扑的映射过程,提出了有向无环图的归约算法,使归约后的图中的顶点数量尽可能地与给定片上网络中的节点数量相同。提出的图归约算法可以有效地识别出所有可归约子图,这些可归约子图可被归约为单一顶点。新算法的适用范围从嵌套图扩展到了任意图,并且拥有与原算法相同的复杂度量级。还提出了一种并行化的算法思想来加速可归约子图的搜索过程。     

Efficient coding of labeled directed acyclic graphs

 We use an adaptation of the Prüfer code for trees to encode labeled directed acyclic graphs, which are often abbreviated to DAGs (or ADGs). In this paper, each DAG is assigned a unique DAG code, which allows an easy handling for several purposes. The set of all possible DAG codes (and therefore the set of all DAGs) for a fixed number of n vertices can be generated efficiently. Furthermore, we are able to rank DAGs, i.e., we provide an algorithm that assigns every DAG a unique number in the set {0,…,a _n −1}, where a _n is the cardinality of the set of labeled DAGs with n≥1 vertices, and we are able to unrank DAGs, which is the inverse operation. We also gain recurrence relations, which can be used to calculate a _n and a _n,q , i.e., the number of DAGs with n vertices and q edges. Finally, it is possible to generate, enumerate, rank and unrank DAGs with given number of edges and also DAGs with bounded indegree. RID="*" ID="*" This research was supported by the Austrian Science Fund (FWF), P13261-INF. I want to thank the reviewers, specially the one who suggested to add the algorithm for unranking DAG codes, for reading the paper very carefully and for the helpful comments.     

Applications of graph theory in computer systems

Many problem situations in computer systems can be analyzed using models based on directed graphs. The vertices of the graph represent states of the system and the directed arcs represent the transitions between these states. This paper is in two parts. The first introduces the concepts of directed graphs and their representations in computers and presents some basic problems and algorithms. The second part examines the application of graph theory to various areas of computer systems.     

Recognition of directed acyclic graphs by spanning tree automata

In this paper, we study tree automata for directed acyclic graphs (DAGs). We define the movement of a tree automaton on a DAG so that a DAG is accepted by a tree automaton if and only if the DAG has a spanning tree accepted by the tree automaton. We call this automaton a spanning tree automaton. The NP-completeness of the membership problem of DAGs for spanning tree automata is shown. However, if inputs are restricted to series–parallel graphs or generalized series–parallel graphs, it is shown that the membership problem for spanning tree automata is solvable in linear time.     

Collective motions and formations under pursuit strategies on directed acyclic graphs

A novel pursuit-based approach is presented to investigate collective motions and formations of a large number of agents with both single-integrator kinematics and double-integrator dynamics on directed acyclic graphs (DAGs). Each agent pursues its neighbors according to a directed acyclic graph, in which the agents without neighbors are leaders. Based on signal flow graph analysis and Mason’s rule, necessary and sufficient conditions are derived for BIBO stability of resulting pursuit systems. Moreover, achievable collective motions and formations are analyzed by adjusting a set of control parameters when leaders keep stationary, perform uniform rectilinear motions, and perform uniform circular motions. Finally, simulations are provided for achieving a static formation and mimicking several complex collective behaviors observed in nature, such as V-formation, vortex motions, and tornado motions.     

Node overlap removal in clustered directed acyclic graphs

Graph drawing and visualization represent structural information as diagrams of abstract graphs and networks. An important subset of graphs is directed acyclic graphs (DAGs). This paper presents a new E-Spring algorithm, extended from the popular spring embedder model, which eliminates node overlaps in clustered DAGs. In this framework, nodes are modeled as non-uniform charged particles with weights, and a final drawing is derived by adjusting the positions of the nodes according to a combination of spring forces and repulsive forces derived from electrostatic forces between the nodes. The drawing process needs to reach a stable state when the average distances of separation between nodes are near optimal. We introduce a stopping condition for such a stable state, which reduces equilibrium distances between nodes and therefore results in a significantly reduced area for DAG visualization. It imposes an upper bound on the repulsive forces between nodes based on graph geometry. The algorithm employs node interleaving to eliminate any residual node overlaps. These new techniques have been validated by visualizing eBay buyer–seller relationships and has resulted in overall area reductions in the range of 45–79%.     

Visualization of graph products

Graphs are a versatile structure and abstraction for binary relationships between objects. To gain insight into such relationships, their corresponding graph can be visualized. In the past, many classes of graphs have been defined, e.g. trees, planar graphs, directed acyclic graphs, and visualization algorithms were proposed for these classes. Although many graphs may only be classified as "general" graphs, they can contain substructures that belong to a certain class. Archambault proposed the TopoLayout framework: rather than draw any arbitrary graph using one method, split the graph into components that are homogeneous with respect to one graph class and then draw each component with an algorithm best suited for this class. Graph products constitute a class that arises frequently in graph theory, but for which no visualization algorithm has been proposed until now. In this paper, we present an algorithm for drawing graph products and the aesthetic criterion graph product's drawings are subject to. We show that the popular High-Dimensional Embedder approach applied to cartesian products already respects this aestetic criterion, but has disadvantages. We also present how our method is integrated as a new component into the TopoLayout framework. Our implementation is used for further research of graph products in a biological context.     

Exploring gene causal interactions using an enhanced constraint-based method

DNA microarray provides a powerful basis for analysis of gene expression. Bayesian networks, which are based on directed acyclic graphs (DAGs) and can provide models of causal influence, have been investigated for gene regulatory networks. The difficulty with this technique is that learning the Bayesian network structure is an NP-hard problem, as the number of DAGs is superexponential in the number of genes, and an exhaustive search is intractable. In this paper, we propose an enhanced constraint-based approach for causal structure learning. We integrate with graphical Gaussian modeling and use its independence graph as an input of our constraint-based causal learning method. We also present graphical decomposition techniques to further improve the performance. Our enhanced method makes it feasible to explore causal interactions among genes interactively. We have tested our methodology using two microarray data sets. The results show that the technique is both effective and efficient in exploring causal structures from microarray data.     

Combinatorial algorithms for feedback problems in directed graphs

Given a weighted directed graph G=(V,A), the minimum feedback arc set problem consists of finding a minimum weight set of arcs A′⊆A such that the directed graph (V,A?A′) is acyclic. Similarly, the minimum feedback vertex set problem consists of finding a minimum weight set of vertices containing at least one vertex for each directed cycle. Both problems are NP-complete. We present simple combinatorial algorithms for these problems that achieve an approximation ratio bounded by the length, in terms of number of arcs, of a longest simple cycle of the digraph.     

Toward continuous pattern detection over evolving large graph with snapshot isolation

This paper studies continuous pattern detection over large evolving graphs, which plays an important role in monitoring-related applications. The problem is challenging due to the large size and dynamic updates of graphs, the massive search space of pattern detection and inconsistent query results on dynamic graphs. This paper first introduces a snapshot isolation requirement, which ensures that the query results come from a consistent graph snapshot instead of a mixture of partial evolving graphs. Second, we propose an SSD (single sink directed acyclic graph) plan friendly to vertex-centric-distributed graph processing frameworks. SSD plan can guide the message transformation and transfer among graph vertices, and determine the satisfaction of the pattern on graph vertices for the sink vertex. Third, we devise strategies for major steps in the SSD evaluation, including the location of valid messages to achieve snapshot isolation, AO-List to determine the satisfaction of transition rule over dynamic graph, and message-on-change policy to reduce outgoing messages. The experiments on billion-edge graphs using Giraph, an open source implementation of Pregel, illustrate the efficiency and effectiveness of our method.     

Searching graphs with A*: applications to job sequencing

The best-first search algorithm A* allows search graphs that are trees, directed acyclic graphs or directed graphs with cycles. In real life applications of A* the search graph is generally implemented as a tree. It is shown here that for certain well known one-machine job sequencing problems that arise in job shops, graph search is much faster than best-first tree search when problem instances are of small and medium size. Moreover, graph search uses less memory and so is able to solve larger problems. Depth-first search needs little memory, and is therefore capable in principle of solving problems of arbitrary size, but is slower than graph search by orders of magnitude for the examples that were studied     

Dynamic monopolies and feedback vertex sets in hexagonal grids

In a majority conversion process, the vertices of a graph can be in one of the two states, colored or uncolored, and these states are dynamically updated so that a vertex becomes colored at a certain time period if at least half of its neighbors were in the colored state in the previous time period. A dynamic monopoly is a set of vertices in a graph that when initially colored will eventually cause all vertices in the graph to become colored. This paper establishes a connection between dynamic monopolies and the well-known feedback vertex sets which are sets of vertices whose removal results in an acyclic graph. More specifically, we show that dynamic monopolies and feedback vertex sets are equivalent in graphs wherein all vertices have degree 2 or 3. We use this equivalence to provide exact values for the minimum size of dynamic monopolies of planar hexagonal grids, as well as upper and lower bounds on the minimum size of dynamic monopolies of cylindrical and toroidal hexagonal grids. For these last two topologies, the respective upper and lower bounds differ by at most one.     

Learning Bayesian Network Classifiers: Searching in a Space of Partially Directed Acyclic Graphs

There is a commonly held opinion that the algorithms for learning unrestricted types of Bayesian networks, especially those based on the score+search paradigm, are not suitable for building competitive Bayesian network-based classifiers. Several specialized algorithms that carry out the search into different types of directed acyclic graph (DAG) topologies have since been developed, most of these being extensions (using augmenting arcs) or modifications of the Naive Bayes basic topology. In this paper, we present a new algorithm to induce classifiers based on Bayesian networks which obtains excellent results even when standard scoring functions are used. The method performs a simple local search in a space unlike unrestricted or augmented DAGs. Our search space consists of a type of partially directed acyclic graph (PDAG) which combines two concepts of DAG equivalence: classification equivalence and independence equivalence. The results of exhaustive experimentation indicate that the proposed method can compete with state-of-the-art algorithms for classification.Editors: Pedro Larrañaga, Jose A. Lozano, Jose M. Peña and Iñaki Inza     

Scheduling algorithms for PIPE (pipelined image-processing engine)

In this paper we present heuristic scheduling algorithms for the National Bureau of Standards/Aspen Inc. Pipelined Image-Processing Engine (PIPE). PIPE is a special-purpose machine for low-level image processing consisting of a linearly connected array of processing stages. A program is specified as a directed acyclic graph (DAG). Our first algorithm schedules planar DAGs. It works top-down through the graph and uses the greedy approach to schedule operations on a stage. It uses several heuristics to control the movement of images between stages. The worst case time for the schedule generated by the algorithm is O(N) times the optimal schedule, where N is the maximum width of the graph. We generalize this algorithm to work on nonplanar graphs, using heuristics for repositioning images on the stages of PIPE. The worst case time for the more general algorithm is also O(N) times the optimal schedule. Finally, we analyze the problem of optimizing throughput and latency for a sequence of DAGs on PIPE.