Coloring Graphs While Avoiding Monochromatic Cycles
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 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 identi fication, 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 real-life instances, the integer-programming algorithm solves the largest instance in about a half hour while the branch-and-check algorithm takes about ten minutes and the backtracking algorithm less than fi ve minutes. Finally, for every algorithm, we also study empirically the transition from a high to a low probability of a YES answer as function of the number of arcs divided by the number of vertices
Year of publication: |
2010
|
---|---|
Authors: | Nobibon, F. Talla |
Other Persons: | Hurkens, Cor (contributor) ; Leus, R. (contributor) ; Spieksma, Frits (contributor) |
Publisher: |
[2010]: [S.l.] : SSRN |
Saved in:
freely available
Extent: | 1 Online-Ressource (29 p) |
---|---|
Type of publication: | Book / Working Paper |
Language: | English |
Notes: | Nach Informationen von SSRN wurde die ursprüngliche Fassung des Dokuments September 2010 erstellt |
Other identifiers: | 10.2139/ssrn.1683889 [DOI] |
Source: | ECONIS - Online Catalogue of the ZBW |
Persistent link: https://www.econbiz.de/10013137722
Saved in favorites
Similar items by person
-
Exact algorithms for coloring graphs while avoiding monochromatic cycles
Talla Nobibon, Fabrice, (2010)
-
Coloring graphs using two colors while avoiding monochromatic cycles
Talla Nobibon, Fabrice, (2012)
-
Robust Maximum Weighted Independent-Set Problems on Interval Graphs
Nobibon, F. Talla, (2011)
- More ...