Document Open Access Logo

Tight Bounds for Online Coloring of Basic Graph Classes

Authors Susanne Albers, Sebastian Schraink

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.7.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Susanne Albers
Sebastian Schraink

Cite AsGet BibTex

Susanne Albers and Sebastian Schraink. Tight Bounds for Online Coloring of Basic Graph Classes. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ESA.2017.7

Abstract

We resolve a number of long-standing open problems in online graph coloring. More specifically, we develop tight lower bounds on the performance of online algorithms for fundamental graph classes. An important contribution is that our bounds also hold for randomized online algorithms, for which hardly any results were known. Technically, we construct lower bounds for chordal graphs. The constructions then allow us to derive results on the performance of randomized online algorithms for the following further graph classes: trees, planar, bipartite, inductive, bounded-treewidth and disk graphs. It shows that the best competitive ratio of both deterministic and randomized online algorithms is Theta(log n), where n is the number of vertices of a graph. Furthermore, we prove that this guarantee cannot be improved if an online algorithm has a lookahead of size O(n/log n) or access to a reordering buffer of size n^(1-epsilon), for any 0 < epsilon <= 1. A consequence of our results is that, for all of the above mentioned graph classes except bipartite graphs, the natural First Fit coloring algorithm achieves an optimal performance, up to constant factors, among deterministic and randomized online algorithms.
Keywords
  • graph coloring
  • online algorithms
  • lower bounds
  • randomization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Avigdor-Elgrabli and Y. Rabani. An optimal randomized online algorithm for reordering buffer management. In Proc. 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1-10, 2013. Google Scholar
  2. A. Bar-Noy, P. Cheilaris, S. Olonetsky, and S. Smorodinsky. Online conflict-free colouring for hypergraphs. Combinatorics, Probability & Computing, 19(4):493-516, 2010. Google Scholar
  3. A. Bar-Noy, P. Cheilaris, and S. Smorodinsky. Deterministic conflict-free coloring for intervals: From offline to online. ACM Trans. Algorithms, 4(4):44:1-44:18, 2008. Google Scholar
  4. D. Bean. Effective coloration. J. Symbolic Logic, 41(2):469-480, 1976. Google Scholar
  5. S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11(1):2-14, 1994. Google Scholar
  6. M. P. Bianchi, H.-J. Böckenhauer, J. Hromkovic, and L. Keller. Online coloring of bipartite graphs with and without advice. Algorithmica, 70(1):92-111, 2014. Google Scholar
  7. H. L. Bodlaender. A tourist guide through treewidth. Acta Cybernetica, 11(1-2):1-21, 1993. Google Scholar
  8. E. Burjons, J. Hromkovic, X. Muñoz, and W. Unger. Online graph coloring with advice and randomized adversary. In Proc. 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'16), pages 229-240. Springer LNCS 9587, 2016. Google Scholar
  9. I. Caragiannis, A. V. Fishkin, C. Kaklamanis, and E. Papaioannou. A tight bound for online colouring of disk graphs. Theoretical Computer Science, 384(2):152-160, 2007. Google Scholar
  10. R. G. Downey and C. McCartin. Online promise problems with online width metrics. Journal of Computer and System Sciences, 73(1):57-72, 2007. Google Scholar
  11. M. Englert, D. Özmen, and M. Westermann. The power of reordering for online minimum makespan scheduling. SIAM J. Comput., 43(3):1220-1237, 2014. Google Scholar
  12. T. Erlebach and J. Fiala. On-line coloring of geometric intersection graphs. Computational Geometry, 23(2):243-255, 2002. Google Scholar
  13. T. Erlebach and J. Fiala. Independence and coloring problems on intersection graphs of disks. In E. Bampis, K. Jansen, and C. Kenyon, editors, Efficient Approximation and Online Algorithms: Recent Progress on Classical Combinatorial Optimization Problems and New Applications, pages 135-155. Springer LNCS 3484, 2006. Google Scholar
  14. Martin Farber. Characterizations of strongly chordal graphs. Discrete Mathematics, 43(2-3):173-189, 1983. Google Scholar
  15. A. Gyárfás and J. Lehel. On-line and first fit colorings of graphs. Journal of Graph Theory, 12(2):217-227, 1988. Google Scholar
  16. M. M. Halldórsson. Parallel and on-line graph coloring. J. Algorithms, 23(2):265-280, 1997. Google Scholar
  17. M. M. Halldórsson and M. Szegedy. Lower bounds for on-line graph coloring. Theoretical Computer Science, 130(1):163-174, 1994. Google Scholar
  18. S. Irani. Coloring inductive graphs on-line. Algorithmica, 11(1):53-72, 1994. Preliminary version in FOCS'90 . Google Scholar
  19. H. A. Kierstead. Coloring graphs on-line. In A. Fiat and G. J. Woeginger, editors, Online Algorithms, pages 281-305. Springer LNCS 1442, 1998. Google Scholar
  20. H. A. Kierstead and W. A. Trotter. An extremal problem in recursive combinatorics. Congressus Numerantium, 33:143-153, 1981. Google Scholar
  21. S. Leonardi and A. Vitaletti. Randomized lower bounds for online path coloring. In Proc. 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM'98), pages 232-247. Springer LNCS 1518, 1998. Google Scholar
  22. L. Lovász, M. Saks, and W. T. Trotter. An on-line graph coloring algorithm with sublinear performance ratio. Annals of Discrete Mathematics, 43:319-325, 1989. Google Scholar
  23. D. Marx. Graph colouring problems and their applications in scheduling. Periodica Polytechnica, Electrical Engineering, 48(1–2):11-16, 2004. Google Scholar
  24. L. Narayanan. Channel assignment and graph multicoloring. Handbook of Wireless Networks and Mobile Computing, pages 71-94, 2004. Google Scholar
  25. D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2):202-208, 1985. Google Scholar
  26. S. Vishwanathan. Randomized online graph coloring. J. Algorithms, 13(4):657-669, 1992. Preliminary version in FOCS'90 . Google Scholar
  27. D. B. West. Introduction to Graph Theory, 2nd Edition. Pearson, 2001. Google Scholar
  28. A. C. C. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proc. 18th Annual Symposium on Foundations of Computer Science, pages 222-227, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact