Document Open Access Logo

Recoloring Interval Graphs with Limited Recourse Budget

Authors Bartłomiej Bosek , Yann Disser , Andreas Emil Feldmann , Jakub Pawlewicz , Anna Zych-Pawlewicz

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.17.pdf
  • Filesize: 0.64 MB
  • 23 pages

Document Identifiers

Author Details

Bartłomiej Bosek
  • Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University in Kraków, Poland
Yann Disser
  • Department of Mathematics, TU Darmstadt, Germany
Andreas Emil Feldmann
  • Department of Applied Mathematics, Charles University in Prague, Czech Republic
Jakub Pawlewicz
  • University of Warsaw, Poland
Anna Zych-Pawlewicz
  • University of Warsaw, Poland

Funding

  • Bosek, Bartłomiej: National Science Centre of Poland, project number 2017/26/D/ST6/00264.
  • Disser, Yann: `Excellence Initiative' of the German Federal and State Governments, and Graduate School CE at TU Darmstadt.
  • Feldmann, Andreas Emil: Czech Science Foundation GAČR (grant #17-10090Y), and Center for Foundations of Modern Computer Science (Charles Univ. project UNCE/SCI/004).
  • Zych-Pawlewicz, Anna: National Science Centre of Poland, project number 2017/26/D/ST6/00264.

Cite AsGet BibTex

Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Jakub Pawlewicz, and Anna Zych-Pawlewicz. Recoloring Interval Graphs with Limited Recourse Budget. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SWAT.2020.17

Abstract

We consider the problem of coloring an interval graph dynamically. Intervals arrive one after the other and have to be colored immediately such that no two intervals of the same color overlap. In each step only a limited number of intervals may be recolored to maintain a proper coloring (thus interpolating between the well-studied online and offline settings). The number of allowed recolorings per step is the so-called recourse budget. Our main aim is to prove both upper and lower bounds on the required recourse budget for interval graphs, given a bound on the allowed number of colors. For general interval graphs with n vertices and chromatic number k it is known that some recoloring is needed even if we have 2k colors available. We give an algorithm that maintains a 2k-coloring with an amortized recourse budget of 𝒪(log n). For maintaining a k-coloring with k ≤ n, we give an amortized upper bound of 𝒪(k⋅ k! ⋅ √n), and a lower bound of Ω(k) for k ∈ 𝒪(√n), which can be as large as Ω(√n). For unit interval graphs it is known that some recoloring is needed even if we have k+1 colors available. We give an algorithm that maintains a (k+1)-coloring with at most 𝒪(k²) recolorings per step in the worst case. We also give a lower bound of Ω(log n) on the amortized recourse budget needed to maintain a k-coloring. Additionally, for general interval graphs we show that if one does not insist on maintaining an explicit coloring, one can have a k-coloring algorithm which does not incur a factor of 𝒪(k ⋅ k! ⋅ √n) in the running time. For this we provide a data structure, which allows for adding intervals in 𝒪(k² log³ n) amortized time per update and querying for the color of a particular interval in 𝒪(log n) time. Between any two updates, the data structure answers consistently with some optimal coloring. The data structure maintains the coloring implicitly, so the notion of recourse budget does not apply to it.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
  • Theory of computation → Online algorithms
  • Theory of computation → Data structures design and analysis
Keywords
  • Colouring
  • Dynamic Algorithms
  • Recourse Budget
  • Interval Graphs

Metrics

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

References

  1. Patrick Baier, Bartłomiej Bosek, and Piotr Micek. On-line chain partitioning of up-growing interval orders. Order, 24(1):1-13, 2007. URL: https://doi.org/10.1007/s11083-006-9050-0.
  2. Luis Barba, Jean Cardinal, Matias Korman, Stefan Langerman, André van Renssen, Marcel Roeloffzen, and Sander Verdonschot. Dynamic graph coloring. In Algorithms and data structures, volume 10389 of Lecture Notes in Comput. Sci., pages 97-108. Springer, Cham, 2017. URL: https://doi.org/10.1007/978-3-319-62127-2_9.
  3. Aaron Bernstein, Jacob Holm, and Eva Rotenberg. Online bipartite matching with amortized O(log² n) replacements. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 947-959. SIAM, Philadelphia, PA, 2018. URL: https://doi.org/10.1137/1.9781611975031.61.
  4. Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic algorithms for graph coloring. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1-20. SIAM, Philadelphia, PA, 2018. URL: https://doi.org/10.1137/1.9781611975031.1.
  5. Bartłomiej Bosek, Stefan Felsner, Kamil Kloch, Tomasz Krawczyk, Grzegorz Matecki, and Piotr Micek. On-line chain partitions of orders: a survey. Order, 29(1):49-73, 2012. URL: https://doi.org/10.1007/s11083-011-9197-1.
  6. Bartłomiej Bosek, H. A. Kierstead, Tomasz Krawczyk, Grzegorz Matecki, and Matthew E. Smith. An easy subexponential bound for online chain partitioning. Electron. J. Combin., 25(2):Paper No. 2.28, 23, 2018. URL: https://doi.org/10.37236/7231.
  7. Bartłomiej Bosek and Tomasz Krawczyk. A subexponential upper bound for the on-line chain partitioning problem. Combinatorica, 35(1):1-38, 2015. URL: https://doi.org/10.1007/s00493-014-2908-7.
  8. Bartłomiej Bosek and Tomasz Krawczyk. On-line partitioning of width w posets into w^O(loglogw) chains. CoRR, arXiv:1810.00270, 2018. URL: http://arxiv.org/abs/1810.00270.
  9. Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, and Anna Zych. Online bipartite matching in offline time. In 55th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2014, pages 384-393. IEEE Computer Soc., Los Alamitos, CA, 2014. URL: https://doi.org/10.1109/FOCS.2014.48.
  10. Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, and Anna Zych-Pawlewicz. Shortest augmenting paths for online matchings on trees. Theory Comput. Syst., 62(2):337-348, 2018. URL: https://doi.org/10.1007/s00224-017-9838-x.
  11. Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, and Anna Zych-Pawlewicz. A tight bound for shortest augmenting paths on trees. In LATIN 2018: Theoretical informatics, volume 10807 of Lecture Notes in Comput. Sci., pages 201-216. Springer, Cham, 2018. URL: https://doi.org/10.1007/978-3-319-77404-6_1.
  12. Marek Chrobak and Maciej Ślusarek. On some packing problem related to dynamic storage allocation. RAIRO Inform. Théor. Appl., 22(4):487-499, 1988. Google Scholar
  13. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT Press, Cambridge, MA, third edition, 2009. Google Scholar
  14. Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to Adwords. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 982-991. ACM, New York, 2008. Google Scholar
  15. Magnús M. Halldórsson and Christian Konrad. Improved distributed algorithms for coloring interval graphs with application to multicoloring trees. In Structural information and communication complexity, volume 10641 of Lecture Notes in Comput. Sci., pages 247-262. Springer, Cham, 2017. URL: https://doi.org/10.1007/978-3-319-72050-0_15.
  16. Makoto Imase and Bernard M. Waxman. Dynamic Steiner tree problem. SIAM J. Discrete Math., 4(3):369-384, 1991. URL: https://doi.org/10.1137/0404033.
  17. Subhash Khot and Ashok Kumar Ponnuswami. Better inapproximability results for MaxClique, chromatic number and Min-3Lin-Deletion. In Automata, languages and programming. Part I, volume 4051 of Lecture Notes in Comput. Sci., pages 226-237. Springer, Berlin, 2006. URL: https://doi.org/10.1007/11786986_21.
  18. Henry A. Kierstead. An effective version of Dilworth’s theorem. Trans. Amer. Math. Soc., 268(1):63-77, 1981. URL: https://doi.org/10.2307/1998337.
  19. Henry A. Kierstead. Recursive ordered sets. In Combinatorics and ordered sets (Arcata, Calif., 1985), volume 57 of Contemp. Math., pages 75-102. Amer. Math. Soc., Providence, RI, 1986. URL: https://doi.org/10.1090/conm/057/856233.
  20. Henry A. Kierstead and William T. Trotter, Jr. An extremal problem in recursive combinatorics. Congr. Numer., 33:143-153, 1981. Google Scholar
  21. Jakub Łącki, Jakub Oćwieja, Marcin Pilipczuk, Piotr Sankowski, and Anna Zych. The power of dynamic distance oracles: efficient dynamic algorithms for the Steiner tree. In STOC'15 - Proceedings of the 2015 ACM Symposium on Theory of Computing, pages 11-20. ACM, New York, 2015. Google Scholar
  22. Dániel Marx. Parameterized coloring problems on chordal graphs. Theoret. Comput. Sci., 351(3):407-424, 2006. URL: https://doi.org/10.1016/j.tcs.2005.10.008.
  23. Nicole Megow, Martin Skutella, José Verschae, and Andreas Wiese. The power of recourse for online MST and TSP. In Automata, languages, and programming. Part I, volume 7391 of Lecture Notes in Comput. Sci., pages 689-700. Springer, Heidelberg, 2012. URL: https://doi.org/10.1007/978-3-642-31594-7_58.
  24. Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. AdWords and generalized online matching. J. ACM, 54(5):Art. 22, 19, 2007. URL: https://doi.org/10.1145/1284320.1284321.
  25. Cara Monical and Forrest Stonedahl. Static vs. dynamic populations in genetic algorithms for coloring a dynamic graph. In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, GECCO '14, pages 469-476, New York, NY, USA, 2014. ACM. URL: https://doi.org/10.1145/2576768.2598233.
  26. Stephan Olariu. An optimal greedy heuristic to color interval graphs. Inform. Process. Lett., 37(1):21-25, 1991. URL: https://doi.org/10.1016/0020-0190(91)90245-D.
  27. Carlos A. S. Oliveira and Panos M. Pardalos. A survey of combinatorial optimization problems in multicast routing. Comput. Oper. Res., 32(8):1953-1981, 2005. URL: https://doi.org/10.1016/j.cor.2003.12.007.
  28. Linda Ouerfelli and Hend Bouziri. Greedy algorithms for dynamic graph coloring. In 2011 International Conference on Communications, Computing and Control Applications, CCCA 2011, pages 1-5, 2011. URL: https://doi.org/10.1109/CCCA.2011.6031437.
  29. Jean-Jacques Pansiot and Dominique Grad. On routes and multicast trees in the internet. SIGCOMM Comput. Commun. Rev., 28(1):41-50, 1998. URL: https://doi.org/10.1145/280549.280555.
  30. Davy Preuveneers and Yolande Berbers. ACODYGRA: An agent algorithm for coloring dynamic graphs. In 6th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pages 381-390, 2004. URL: https://lirias.kuleuven.be/1654548.
  31. Fred S. Roberts. Indifference graphs. In Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), pages 139-146. Academic Press, New York, 1969. Google Scholar
  32. Scott Sallinen, Keita Iwabuchi, Suraj Poudel, Maya Gokhale, Matei Ripeanu, and Roger Pearce. Graph colouring as a challenge problem for dynamic graph processing on distributed systems. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC '16, pages 30:1-30:12, Piscataway, NJ, USA, 2016. IEEE Press. URL: http://dl.acm.org/citation.cfm?id=3014904.3014945.
  33. Shay Solomon and Nicole Wein. Improved dynamic graph coloring. In 26th European Symposium on Algorithms, volume 112 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 72, 16. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018. Google Scholar
  34. Mario Valencia-Pabon. Revisiting Tucker’s algorithm to color circular arc graphs. SIAM J. Comput., 32(4):1067-1072, 2003. URL: https://doi.org/10.1137/S0097539700382157.
  35. Long Yuan, Lu Qin, Xuemin Lin, Lijun Chang, and Wenjie Zhang. Effective and efficient dynamic graph coloring. Proc. VLDB Endow., 11(3):338-351, 2017. URL: https://doi.org/10.14778/3157794.3157802.
  36. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 681-690. ACM, New York, 2006. URL: https://doi.org/10.1145/1132516.1132612.
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