Trade-Offs in Dynamic Coloring for Bipartite and General Graphs
Tóm tắt
The dynamic coloring problem has gained attention in the recent past. The focus has largely been on obtaining efficient update time algorithms using
$$\Delta +1$$
or more colors and the trade-offs between update time and query time. Another important parameter in dynamic coloring is the number of recolorings per update which is addressed by the works of Barba et al. in WADS’17, and Solomon and Wein in ESA’18. In SODA’18, Bhattacharya et al. presented a randomized algorithm that uses
$$\Delta +1$$
colors and achieves amortized
$$O(\log \Delta )$$
update time. In STACS’20, Henzinger and Peng presented a randomized
$$(\Delta +1)$$
-coloring algorithm with amortized O(1) update time. Independently on arXiv, Bhattacharya et al. also presented a randomized
$$(\Delta +1)$$
-coloring algorithm with amortized O(1) update time. While works of Bhattacharya et al., and Henzinger and Peng are very efficient in terms of update time, they do not address the number of recolorings per update. We bridge this gap by providing efficient update time algorithms with constant number of recolorings. Moreover our algorithm is deterministic as opposed to the works of Bhattacharya et al. in SODA’18, and Henzinger and Peng in STACS’20. Next, we study bipartite graphs which can be optimally colored in the static setting. We show that even in the incremental setting (where edges are added to the graph and no edge can be deleted), there is a bad update sequence which forces the update time to be at least
$$\Omega (\log {n})$$
in the amortized setting and
$$\Omega (n)$$
in the worst case. This possibly explains the lack of any results on dynamic coloring specific to bipartite graphs. We circumvent this lower bound by proposing two approaches. Firstly, we allow the use of more than two colors and obtain significantly better update time. Second, we introduce the idea of implicit coloring. If the color of a vertex is explicitly stored in a data structure and updated at end of every update then we call such an algorithm as explicit coloring algorithm. All prior work on dynamic coloring uses explicit coloring algorithms. We show that using implicit coloring we can obtain near constant update time and query time for incremental coloring for bipartite case. We also bound the number of recolorings to near constant. We also show an efficient implicit fully dynamic algorithm for bipartite graphs. All our algorithms are deterministic and use simple data structures. Hence, we believe that our algorithms are of practical importance.
Tài liệu tham khảo
Assadi, S., Onak, K., Schieber, B., Solomon, S.: Fully dynamic maximal independent set with sublinear update time. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 815–826 (2018)
Barba, L., Cardinal, J., Korman, M., Langerman, S., Renssen, A.V., Roeloffzen, M., Verdonschot, S.: Dynamic graph coloring. In: Algorithms and Data Structures—15th International Symposium, WADS 2017, pp. 97–108 (2017)
Bhattacharya, S., Chakrabarty, D., Henzinger, M., Nanongkai, D.: Dynamic algorithms for graph coloring. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp. 1–20 (2018)
Bhattacharya, S., Grandoni, F., Kulkarni, J., Liu, Q.C., Solomon, S.: Fully dynamic (\(\Delta \)+1)-coloring in constant update time. CoRR. arXiv:1910.02063 (2019)
Brodal, G.S., Fagerberg, R.: Dynamic representation of sparse graphs. In: Algorithms and Data Structures, 6th International Workshop, WADS, pp. 342–351 (1999)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, Appendix B, 3rd edn., pp. 1180–1181. The MIT Press, Cambridge (2009)
Fredman, M., Saks, M.: The cell probe complexity of dynamic data structures. In: Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, STOC ’89 (1989)
Fredman, M.L., Willard, D.E.: BLASTING through the information theoretic barrier with FUSION TREES. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 1–7. ACM (1990)
Henzinger, M.R., King, V.: Randomized dynamic graph algorithms with polylogarithmic time per operation. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pp. 519–527 (1995)
Henzinger, M., Peng, P.: Constant-time dynamic (\(\Delta 1\))-coloring. In: 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, pp. 53:1–53:18 (2020)
Henzinger, M., Neumann, S., Wiese, A.: Explicit and implicit dynamic coloring of graphs with bounded arboricity. CoRR (2020)
Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723–760 (2001)
Kashyop, M.J., Narayanaswamy, N.S., Nasre, M., Potluri, S.M.: Dynamic coloring for bipartite and general graphs. CoRR. arXiv:1909.07854 (2019)
Lovász, L., Saks, M.E., Trotter, W.T.: An on-line graph coloring algorithm with sublinear performance ratio. Discrete Math. 75(1–3), 319–325 (1989)
Miltersen, P.B. Cell probe complexity—a survey. In: In 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 1999. Advances in Data Structures Workshop (1999)
Nash-Williams, C.S.J.A.: Decomposition of finite graphs into forests. J. Lond. Math. Soc. s1–39(1), 12 (1964)
Neiman, O., Solomon, S.: Simple deterministic algorithms for fully dynamic maximal matching. In: Symposium on Theory of Computing Conference, STOC’13, pp. 745–754 (2013)
Pǎtraşcu, M.: Unifying the landscape of cell-probe lower bounds. CoRR. arXiv:1010.3783
Pǎtraşcu, M., Demaine, E.D.: Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35(4), 932–963 (2006)
Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362–391 (1983)
Solomon, S.: Fully dynamic maximal matching in constant update time. In: IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pp. 325–334 (2016)
Solomon, S., Wein, N.: Improved dynamic graph coloring. In: 26th Annual European Symposium on Algorithms, ESA 2018, pp. 72:1–72:16 (2018)