
Algorithms Algorithms and Data Structures  Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum 
 LinkBack  Thread Tools  Display Modes 
October 31st, 2009, 12:58 PM  #1  
Joined: Oct 2009 Posts: 4  Finding an acyclic orientation in a graph
Hi, I'm having some difficulty with the following question: Quote:
Thanks in advance!  
My Computer Forum is free to register and we welcome everyone! 
January 21st, 2010, 12:42 AM  #2 
Joined: Dec 2009 Posts: 7  Re: Finding an acyclic orientation in a graph
Hi, The problem is NPHard. It can be easily reduced to Hamiltonian cycle problem. And no polynomial time algorithm is known for Hamiltonian cycle. I am not sure if any approximation algorithm exists ? 
January 21st, 2010, 06:05 AM  #3  
Joined: Oct 2009 Posts: 4  Re: Finding an acyclic orientation in a graph
Hi, Thanks for the reply. Here is the solution for the problem: Quote:
 
January 21st, 2010, 10:22 AM  #4 
Joined: Dec 2009 Posts: 7  Re: Finding an acyclic orientation in a graph
This is a very interesting observation. Thanks. Since I have learned NPcompleteness, rather than finding if polynomial time algorithm for a problem I tend to prove it NPhard. 
January 24th, 2010, 04:20 AM  #5 
Joined: Dec 2009 Posts: 7  Re: Finding an acyclic orientation in a graph
How about this counter example? It has a directed cycle and a vertex that has zero out degree. Do you have a proof of your algorithm? 
January 24th, 2010, 04:42 AM  #6 
Joined: Oct 2009 Posts: 4  Re: Finding an acyclic orientation in a graph
The algorithm takes as input an undirected graph and a function D:V>N. Could you please explicitly state the two for you counter example? 
January 24th, 2010, 01:17 PM  #7 
Joined: Dec 2009 Posts: 7  Re: Finding an acyclic orientation in a graph
This is an example of an orientation with a directed cycle and a zero out degree vertex. I am yet not sure about the D:VN function. If you could give an example input I might specify the function for this instance. 
January 24th, 2010, 01:28 PM  #8  
Joined: Oct 2009 Posts: 4  Re: Finding an acyclic orientation in a graph Quote:
The algorithms then concludes if G has an acyclic orientation G' such that for each v in V , its outdegree (the number of edges going out of it) in G' is D(v). For example, a legal input would be: G={V,E} V={a,b,c} E={(a,b),(b,c),(c,a)} D:V>N D(a)=1 D(b)=1 D(c)=0 This means that we want the result graph to have one edge going out of a, one out of b, and no edges going out of c. The algorithm is supposed to tell us if for the given input, an acyclic orientation is possible.  

Tags 
acyclic, finding, graph, orientation 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
help me for finding gboxapp software  jamiulislam  Computer Science  0  January 21st, 2013 03:02 AM 
Help in finding a high performance notebook!  deanSs  Computer Hardware  2  February 9th, 2012 01:55 PM 
decide if a graph contains a triangle  becko  Algorithms  2  December 28th, 2011 12:50 PM 
Finding large 2primes  NClement  Computational Science  13  August 7th, 2008 06:03 AM 
Finding clusters of points on a grid  circleBounding  Algorithms  2  February 10th, 2008 06:09 PM 