Acyclicity Tests in Classes of Dense Digraphs in Streaming Model

Abstract

Graph is a popular model to represent highly structured data which involves entities who have pairwise relations between them. In many applications, computing graph theoretic properties after modelling the entire dataset as graph, provides us interesting informations which gives us insights about the whole dataset. However, in case of application, the datasets in question can be so large that it's di cult to store in the main memory and the dataset can even be dynamic(can change with time). These days in so many applications, the algorithm that requires to solve the problem which takes massive dataset as input, has limitations on time as well as space taken to store the information. These constraints leads us for the development of new techniques. Streaming model of computation takes all these challenges into account and provides us solutions with limited resources in cost of accuracy. Graph stream is a sequence of imcoming edges and we are only allowed to insert(insertion only model) or both insert and delete(dynamic model) into an initially empty graph. Finally our objective is to nd out certain properties of the graph at the end of the stream which minimizes the amount of space the algorithm uses. Sometimes this algorithm needs to provide the trade of between the space usage and the time taken. There is a large volume work on undirected graphs in streaming model but the area of directed graph stream is a pretty unexplored. In this project, we study the problem of testing acyclicity in dense digraphs in semi-streaming model. Here the graph on n vertices is presented as a stream of edges and using O(n polylog(n))-space, we must determine if it is acyclic or not