ORBEL 24 - annual conference of the Belgian Operational Research society edition:24 location:Liège (Belgium) date:28-29 January 2010
We consider the problem of deciding whether a given directed graph can be vertex-partitioned into two acyclic subgraphs. Applications of this problem include testing rationality of collective consumption behavior, a subject in micro-economics. We present an exact algorithm called a branch-and-check algorithm, which is able to solve instances of considerable size within few seconds. We study empirically the transition from a high to a low probability of YES answer as function of some problem parameters. We identify classes of directed graphs for which the problem is easy and prove that the existence of a constant factor approximation algorithm is unlikely for an optimization version which maximizes the number of vertices that can be colored using two colors while avoiding monochromatic cycles.