This question has a great answer for detecting cycles in a directed graph. Unfortunately, it does not seem easy to make a Map Reduce version of it.

Specifically, I am interested in a Map Reduce algorithm for removing cycles from a directed graph.

I have evaluated using a breadth first search (BFS) algorithm but an issue I see is that two different edges may be removed simultaneously to cut off a cycle. The impact of this scenario is that too many edges could be removed. It is important that cycles are removed while minimizing the number of edges removed.

Solutions with proofs available are preferred!

Thanks.

You need an iterative map reduce to implement this algorithm. See http://www.iterativemapreduce.org/ for a map-reduce framework that centers around iterative map reduces. Or http://www.johnandcailin.com/blog/cailin/breadth-first-graph-search-using-iterative-map-reduce-algorithm for a worked example of how to do a breadth-first search through a graph with Hadoop using an iterative map reduce.

Well if you want to remove all cycles, then you will end up with a tree. So no matter what algorithm you use, you will remove |E| - (n -1) edges. (if it was correct of course)

However, the question is whether the deletion of edges will lead to a disconnected graph. For this you will need to make an ordering of the edges (let's say lexicographic order). You should then always remove the the largest edge in a cycle. [I guess the proof of correctness is very direct whence: simply use Kruskal algorithm and find that they will be the same ! ]

Any spanning tree algorithm would solve the problem for you. Depending on what you want to optimize (either time or messsage complexity or any other perfomance metric), you will find different algorithms. BFS is the best for time. No algorithm can solve the problem for less than c(logn + m) message for c > 0.

There is an algoritm I like using for DAG's is called YO-YO. The description of the algorithm can be found in : http://www.site.uottawa.ca/~flocchin/CSI4509/8-yoyo11_fr.pdf

Similar Questions

Do you know an application or algorithm to reduce dimensionality of big data, maybe using Map-Reduce, or other api, also: Do you know some algorithms like Singular Value decomposition than can be us

I'm trying to evaluate the differences between these two options. Here are some pros and cons I can think of : Elastic Map Reduce => Better support from Amazon, No need to administer cluster, More

For designing some algorithm I need to simulate the map-reduce environment. I assume that I have couple of jobs and each of them consists of set of map and reduce tasks. I have to make assumption abou

I am able to clear the polygons after 5 seconds passes once the tiles are loaded on the map, but when I try to build the polygons again the polygons are being generated by the original data. I would l

I'm looking for an approximation algorithm for the following problem - I have an unweighted, undirected graph, with cycles, and want to find the longest path starting from a given node. I do value spe

I have an undirected graph. One edge in that graph is special. I want to find all other edges that are part of a even cycle containing the first edge. I don't need to enumerate all the cycles, that wo

Ive seen big data queuing jobs that are performant for real time work because they produce data that is readily consumed. Map/Reduce jobs (hadoop) are performant for a different reason : they are offl

I have written an algorithm which does (some sort of) 'topological sorting' (not exact). This algorithm copies the given graph and then manipulates the copy (by removing edges). On a million node boos

How can I access data from collectionB within the map part of a map/reduce being performed on collectionA? If it helps, I have phrases stored in collectionA which I want to split each phrase into in

I am trying to run HIPI map reduce example (Downloader). I have added the hipi jars to the build path but getting below error on execution. My command looks like, hadoop jar Downloader.jar Downloader

I want to read multiple files from multiple directories in Map-Reduce program. I have tried to give the filename in main method: as FileInputFormat.setInputPaths(conf,new Path(hdfs://localhost:54310/

What is a simple algorithm to determine if a graph, given as an adjacency matrix, is a tree?

Consider this graph: The second image (with weights in parenthesis) is balanced, i.e. each node sends the right amount of weight to the other nodes, and the end node has the same weight as the star

In mongoid 2, this used to work: mr_collection = self.collection.map_reduce(map, reduce, { :query => query, :finalize => finalize, :out => {:replace => 'mr_results'} }) limit = (options[:l

Given an adjacency list representation of a directed multigraph is there a O(V+E) algorithm to convert it into undirected simple graph? The algorithm obiviously should use minimal space.

I noticed that usually when hadoop cluster is not busy, before map side is completely done, reduce side starts progressing? How is that possible? I remember reading somewhere that reduce progress indi

If the following is used Analytic.collection.map_reduce(map, reduce, :query => {:page => subclass_name}, :sort => [[:pageviews, Mongo::DESCENDING]]).find.to_a it won't sort by pageviews. Alt

I've to perform a map reduce operation with a clustering algorithm of a large amount of data. I've choose MongoDB for its scalability, great docs, BSon documents storage and many other great features.

Im working on some path finding stuff and ran into an issues I need help with. I have a 2D grid of evenly spaced nodes. I need an algorithm to find all 8 neighbors (if they exist) for each node so I c

I'm struggling with RavenDB's multi map/reduce concept and recently asked this question regarding how to properly write a multi map/reduce index. I got the simple index in that question working but wh

Is it possible to combine statebox and map/reduce in riak? Can not find any examples, and statebox riak api does not provide any kind of map/reduce functionality as well.

I am trying to remove the same key from two maps using reflection. However, removing it from the first map is causing a change to the key value. Is this WAI or a bug. Code at (http://play.golang.org/p

I have a simple graph constructed using NetworkX as follows: import networkx as nx import matplotlib.pyplot as plt G = nx.DiGraph() G.add_edges_from([(0,1), (0,2), (1,1), (1,2)]) nx.draw_networkx(G) p

It is easy to understand how map-reduce is used to collect text and build a large inverted index. But how can map-reduce be used in inverted index search?

How do I access the output from the following mongoDB map reduce code? I assume that the map reduce function is producing a collection called 'session_stat' with fields: 'dayOfWeek' and 'count' that I

I am writing a simple program in SWI-Prolog to run through a directed graph, from one node to the next. I'm having trouble avoiding cycles though and would like some help. Each edge has a cost associa

I am getting a red line/strip in the map. I am trying to remove this line. do any one know how to remove this? I guess they are called something like bus routes. It appears along with the yellow borde

I've been trying Cascading, but I cannot see any advantage over the classic map reduce approach for writing jobs. Map Reduce jobs gives me more freedom and Cascading seems to be putting a lot of obsta

I want to run a simple example of word count with map reduce. but I have this problem and have no idea how to solve it. Exception in thread main java.lang.VerifyError: Bad type on operand stack Exce

I'm trying to determine the cycles in a directed graph using Tarjan's algorithm, presented in his research paper Enumeration of the elementary circuits of a directed graph from Septermber 1972. I'm

I am newbie on Hadoop. I remember I learned from somewhere that in Hadoop, all map functions have to be completed before reduce functions can start off. But I just got the printout when I run a map re

I'm trying to simulate the following game: The game is played with 2 players. Imagine you have a graph, with vertices and edges. Each turn you can remove one edge, if you isolate a vertex you get a po

I'm new to the map reduce concept and even though I'm making some slow progress, I'm finding some issues that I need some help with. I have a simple collection consisting of an id, city and and destin

How can I find (iterate over) ALL the cycles in a directed graph from/to a given node? For example, I want something like this: A->B->A A->B->C->A but not: B->C->B

I have to write a Map Reduce job in Java in which I am given Locations (City, State, Country) and I need to convert them to lat/long coordinates, the details of which are provided from an external web

From the digging I've done it looks like I want to use .on but I'm note sure how to go about implementing it. I'm still learning javascript and jquery so I could be missing something... The code belo

Given that I have an initially empty graph, to which will, incrementally, be added edges (one by one), what would be the best way to detect and identify appearing cycles? Would I have to check for cyc

I have a Map<Something, List<String>> map. I want to remove a String from the List<String>. Is that possible ? How do I do that ? I don't want to remove the mapping, just alter the '

For some reason I'm only getting a null key from map/reduce result in couchdb on mac Result: {rows:[ {key:null,value:2224} ]} Im using couchapp v8.1 and couchdb v1.0.2 My map function is: funct

I'm very new to web development and I wrote code to take user input from a form, build a graph from it and run a graphing algorithm on it. At first, I sent the text using a post request but the algori

I'm new to Amazon web services, I'm trying to run job flows on Amazon elastic map reduce jobs using command line interface tools. I followed the steps from amazon developer guide of this developer gui

I am new to map / reduce and trying to figure out a way to collect the following data using map / reduce instead doing it my my (slow) application logic: I have a collection 'projects' with a 1:n rela

I'm running Hadoop version 1.0.0 on a cluster of about 500 nodes. My job has about 3000 map tasks and 10 reduce tasks. The map tasks complete after about 4 hours (as expected). The reduce tasks each c

Consider the following question relative to graph theory : Let G a bipartite graph. To make the problem more concrete suppose G is the disjoint union of two sets, say I and S. Suppose I represents In

I am newbie to write couchdb map and reduce queries. One of my requirements is based on some keys we have to emit the data. i wrote Successfully for that as mentioned below. function(doc) { emit([doc.

I get edges from canny algorithm, but between lines are little spaces. I need to connect lines together and reduce this space. For example: example image I work with opencv in Android. Has anyone an

Is there any matrix completion algorithm which can be used to to reconstruct a graph using only a small number of its edges? There are many algorithms to recover and complete an unknown matrix which

Recently I read a paper that proposed algorithm for mining Maximum Contiguous patterns from DNA data. The proposed method, which sounds pretty interesting, used the following model of MapReduce. map-&

I have a directed graph, and I want to find the maximal amount of flow that I can send along cycles(loops). Can the standard Ford-Fulkerson approach work, with augmenting paths(cycles in this case), o

I don't use Reduce part of my indexes. Instead of that I use Where clause for my Map index queries. What is the difference between these two approaches: to use Reduce part of the Map-Reduce index or u