Exact algorithms for coloring graphs while avoiding monochromatic cycles

F. Talla Nobibon, C.A.J. Hurkens, R. Leus, F.C.R. Spieksma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

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 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. 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 few seconds; however, the CPU time of the integer-programming algorithm increases with the number of vertices in the graph while that of the two other procedures does not. For every algorithm, we also study empirically the transition from a high to a low probability of YES answer as function of a parameter of the problem. For real-life instances, the integer-programming algorithm fails to solve the largest instance after one hour while the other two algorithms solve it in about ten minutes.
Original languageEnglish
Title of host publicationAlgorithmic Aspects in Information and Management (6th International Conference, AAIM 2010, Weihai, China, July 19-21, 2010. Proceedings)
EditorsB. Chen
Place of PublicationBerlin
PublisherSpringer
Pages229-242
ISBN (Print)978-3-642-14354-0
DOIs
Publication statusPublished - 2010
Event6th Algorithmic Aspects in Information and Management International Conference (AAIM 2010) - Weihai, China
Duration: 19 Jul 201021 Jul 2010
Conference number: 6

Publication series

NameLecture Notes in Computer Science
Volume6124
ISSN (Print)0302-9743

Conference

Conference6th Algorithmic Aspects in Information and Management International Conference (AAIM 2010)
Abbreviated titleAAIM 2010
CountryChina
CityWeihai
Period19/07/1021/07/10

Fingerprint Dive into the research topics of 'Exact algorithms for coloring graphs while avoiding monochromatic cycles'. Together they form a unique fingerprint.

Cite this