My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Algorithms

Algorithms Algorithms and Data Structures - Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum


Reply
 
LinkBack Thread Tools Display Modes
October 31st, 2009, 11:58 AM   #1
 
Joined: Oct 2009
Posts: 4
Finding an acyclic orientation in a graph

Hi,

I'm having some difficulty with the following question:

Quote:
Given an undirected graph G = (V,E), an orientation of G is a directed graph G' = (V,E'),
such that for each undirected edge {u,v} in E, exactly one of the directed edges (u,v) and
(v,u) is in E'. An orientation is called acyclic if the graph G' contains no directed cycles.
You are given an undirected graph G and a function D : V-> N. Design an algorithm that
decides whether G has an acyclic orientation G' such that for each v in V , its out-degree (the
number of edges going out of it) in G' is D(v).
Does anyone have a direction or hint?

Thanks in advance!
Anonymous Coward is offline  
 

My Computer Forum is free to register and we welcome everyone!

January 20th, 2010, 11:42 PM   #2
 
Joined: Dec 2009
Posts: 7
Re: Finding an acyclic orientation in a graph

Hi,
The problem is NP-Hard. 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 ?
vin.san is offline  
January 21st, 2010, 05: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:
Note that in an acyclic directed graph, at least one of the vertices has an out-degree of 0.
Otherwise, we could take a walk on the graph. The walk will never cross the same vertex
twice, because the graph is acyclic. Therefore, because all vertices have out-degree at least 1,
the walk will carry on inde nitely.
Our algorithm will check wether there is a vertex with out degree 0 in D. If there is none,
then there cannot be an appropriate orientation. If there is one, we know how to orient all
its adjacent edges, so we may orient those edges, erase the vertex from the original graph and
update D accordingly. If an acyclic orientation exists, it remains acyclic after the removal of
a vertex, so we will carry on until there are no more vertices in the original graph.

Code:
Orient(V,E,D)
   V' =  V
   E' = null
   While (V is not Empty)
      If (exists v in V such that D(v) = 0)
         Forall ((v,u) in E)
            E =  E \ {(v, u)}
            E' =  E Union {(u, v)} // (oriented as going into v)
            D(u) = D(u) - 1
         End
         V =  V \ {v}
    Else
      Output FAIL
       Exit
    Endif
End
Anonymous Coward is offline  
January 21st, 2010, 09: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 NP-completeness, rather than finding if polynomial time algorithm for a problem I tend to prove it NP-hard.
vin.san is offline  
January 24th, 2010, 03: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?
vin.san is offline  
January 24th, 2010, 03: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?
Anonymous Coward is offline  
January 24th, 2010, 12: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:V-N function.
If you could give an example input I might specify the function for this instance.
vin.san is offline  
January 24th, 2010, 12:28 PM   #8
 
Joined: Oct 2009
Posts: 4
Re: Finding an acyclic orientation in a graph

Quote:
You are given an undirected graph G and a function D : V-> N.
The algorithm needs an undirected graph G and a function D:V->N in order to work.
The algorithms then concludes if G has an acyclic orientation G' such that for each v in V , its out-degree (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.
Anonymous Coward is offline  
Reply

  My Computer Forum > Computer Science Forum > Algorithms

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 02:02 AM
Help in finding a high performance notebook! deanSs Computer Hardware 2 February 9th, 2012 12:55 PM
decide if a graph contains a triangle becko Algorithms 2 December 28th, 2011 11:50 AM
Finding large 2-primes NClement Computational Science 13 August 7th, 2008 05:03 AM
Finding clusters of points on a grid circleBounding Algorithms 2 February 10th, 2008 05:09 PM





Copyright © 2018 My Computer Forum Forum. All rights reserved.