Article (Scientific journals)
Coloring Graphs Using Two Colors while Avoiding Monochromatic Cycles
Talla Nobibon, Fabrice; Hurkens, Cor A. J.; Leus, Roel et al.
2011In INFORMS Journal on Computing
Peer Reviewed verified by ORBi
 

Files


Full Text
coloringgraph_report.pdf
Publisher postprint (1.01 MB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
directed graph; undirected graph; bipartite graph; acyclic graph; phase transition; NP-complete
Abstract :
[en] 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 microeconomics. We prove that the problem is NP-complete even for oriented graphs and argue that the existence of a constant-factor approximation algorithm is unlikely for an optimization version that maximizes the number of vertices that can be colored using two colors while avoiding monochromatic cycles. We present three exact algorithms—namely, an integer-programming algorithm based on cycle identification, a backtracking algorithm, and a branch-and-check algorithm. We compare these three algorithms both on real-life instances and on randomly generated graphs. We find that for the latter set of graphs, every algorithm solves instances of considerable size within a few seconds; however, the CPU time of the integer-programming algorithm increases with the number of vertices in the graph more clearly than the CPU time of the two other procedures. For real-life instances, the integer-programming algorithm solves the largest instance in about a half hour, whereas the branch-and-check algorithm takes approximately 10 minutes and the backtracking algorithm less than 5 minutes. Finally, for every algorithm, we also study empirically the transition from a high to a low probability of a YES answer as a function of the number of arcs divided by the number of vertices.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Talla Nobibon, Fabrice ;  Université de Liège - ULiège > HEC-Ecole de gestion : UER > UER Opérations : Supply Chain Management
Hurkens, Cor A. J.
Leus, Roel
Spieksma, Frits
Language :
English
Title :
Coloring Graphs Using Two Colors while Avoiding Monochromatic Cycles
Publication date :
2011
Journal title :
INFORMS Journal on Computing
ISSN :
1091-9856
eISSN :
1526-5528
Publisher :
INFORMS: Institute for Operations Research
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 26 August 2011

Statistics


Number of views
90 (1 by ULiège)
Number of downloads
690 (4 by ULiège)

Scopus citations®
 
4
Scopus citations®
without self-citations
3
OpenCitations
 
4

Bibliography


Similar publications



Contact ORBi