Finding an acyclic orientation in a graph

[Anonymous Coward]

Hi,

I'm having some difficulty with the following question:

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]

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]

Hi,

Thanks for the reply.

Here is the solution for the problem:

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: Select all

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]

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]

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]

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]

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]

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.