Title: Coloring graphs to avoid monochromatic cycles
Authors: Talla Nobibon, Fabrice
Hurkens, Cor
Leus, Roel
Spieksma, Frederik #
Issue Date: 2010
Conference: ORBEL 24 - annual conference of the Belgian Operational Research society edition:24 location:Liège (Belgium) date:28-29 January 2010
Abstract: 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.
Publication status: published
KU Leuven publication type: IMa
Appears in Collections:Research Center for Operations Research and Business Statistics (ORSTAT), Leuven
# (joint) last author

Files in This Item:

There are no files associated with this item.


All items in Lirias are protected by copyright, with all rights reserved.