Finding an acyclic orientation in a graph

Anonymous Coward · October 31st, 2009, 12:58 PM

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!

vin.san · January 21st, 2010, 12:42 AM

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 ?

Anonymous Coward · January 21st, 2010, 06:05 AM

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 indenitely.
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

vin.san · January 21st, 2010, 10:22 AM

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 · January 24th, 2010, 04:20 AM

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?

Anonymous Coward · January 24th, 2010, 04:42 AM

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?

vin.san · January 24th, 2010, 01:17 PM

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.

Anonymous Coward · January 24th, 2010, 01:28 PM

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.

January 21st, 2010, 12:42 AM	#2
vin.san 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 ?

January 21st, 2010, 10:22 AM	#4
vin.san 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.

January 24th, 2010, 04:20 AM	#5
vin.san 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
Anonymous Coward 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
vin.san 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.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

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 2-primes	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