Dynamic data structures for interval coloring
We consider the dynamic graph coloring problem restricted to the class of interval graphs in the incremental and fully dynamic setting. The input consists of a sequence of intervals that are to be either colored, or deleted, if previously colored. For the incremental setting, we consider the well studied optimal online algorithm (KT-algorithm) for interval coloring due to Kierstead and Trotter [1]. We present the following results on the dynamic interval coloring problem. ■ Any direct implementation of the KT-algorithm requires Ω(Δ2) time per interval in the worst case. ■ There exists an incremental algorithm which supports insertion of an interval in amortized O(logn+Δ) time per update and maintains a proper coloring using at most 3ω−2 colors. ■ There exists a fully dynamic algorithm which supports insertion of an interval in O(logn+Δlogω) update time and deletion of an interval in O(Δ2logn) update time in the worst case and maintains a proper coloring using at most 3ω−2 colors. The KT-algorithm crucially uses the maximum clique size in an induced subgraph in the neighborhood of a given vertex. We show that the problem of computing the induced subgraph among the neighbors of a given vertex has the same hardness as the online boolean matrix vector multiplication problem [2]. We show that ■ Any algorithm that computes the induced subgraph among the neighbors of a given vertex requires at least quadratic time unless the OMv conjecture [2] is false. Finally, we obtain the following result on the OMv conjecture. ■ If the matrix and the vectors in the online sequence have the consecutive ones property, then the OMv conjecture [2] is false.
An Invitation to Dynamic Graph Problems: Upper Bounds — II
In this section of Resonance, we invite readers to pose questions likely to be raised in a classroom situation. We may suggest strategies for dealing with them, or invite responses, or both. “Classroom” is equally a forum for raising broader issues and sharing personal experiences and viewpoints on matters related to teaching and learning science. We present a three-part article consisting of a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science community. This article presents the second part of the survey consisting of a set of techniques to prove upper bounds for dynamic graph problems. In the first part of the survey, we presented motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the third part of the survey, we will present a set of techniques to prove lower bounds for dynamic graph problems. A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Though classic problems like coloring, matching, independent set, and many more are extensively studied for static graphs, we are still far from obtaining a complete set of upper bound results for their dynamic graph counterparts. The upper bound techniques used in dynamic graphs need attention from an implementation perspective, along with theoretical advances. The practical potential of these techniques is yet to be explored. We invite undergraduate researchers and programmers to consider an efficient implementation of these techniques through this three-part survey.
Lazy or eager dynamic matching may not be fast
We consider two sub-classes of fully dynamic algorithms for maintaining a maximal matching, which we define as lazy algorithms and eager algorithms. We prove a conditional lower bound which is sub-linear in the number of edges for the update time of lazy algorithms and eager algorithms. Our result is conditioned on the well known conjecture about the hardness of triangle detection in a graph.
Trade-Offs in Dynamic Coloring for Bipartite and General Graphs
The dynamic coloring problem has gained attention in the recent past. The focus has largely been on obtaining efficient update time algorithms using Δ + 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 Δ + 1 colors and achieves amortized O(log Δ) update time. In STACS’20, Henzinger and Peng presented a randomized (Δ + 1) -coloring algorithm with amortized O(1) update time. Independently on arXiv, Bhattacharya et al. also presented a randomized (Δ + 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 Ω (log n) in the amortized setting and Ω (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.
Data Structures for Incremental Interval Coloring
We consider the dynamic graph coloring problem restricted to the class of interval graphs. At each update step the algorithm is presented with an interval to be colored, or a previously colored interval to delete. The goal of the algorithm is to efficiently maintain a proper coloring of the intervals with as few colors as possible by an online algorithm. In the incremental model, each update step presents the algorithm with an interval to be colored. The problem is closely connected to the online vertex coloring problem of interval graphs for which the Kierstead-Trotter (KT) algorithm achieves the best possible competitive ratio. We first show that a sub-quadratic time direct implementation of the KT-algorithm is unlikely to exist conditioned on the correctness of the Online Boolean Matrix Vector multiplication conjecture due to Henzinger et al. [9]. We then design an incremental algorithm that is subtly different from the KT-algorithm and uses at most 3ω − 2 colors, where ω is the maximum clique in the interval graph associated with the set of intervals. Our incremental data structure maintains a proper coloring in amortized O(log n+Δ) update time where n is the total number of intervals inserted and Δ is the maximum degree of a vertex in the interval graph.
An Invitation to Dynamic Graph Problems: Basics — I
In this section of Resonance, we invite readers to pose questions likely to be raised in a classroom situation. We may suggest strategies for dealing with them, or invite responses, or both. “Classroom” is equally a forum for raising broader issues and sharing personal experiences and viewpoints on matters related to teaching and learning science. We present a three-part article comprising a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science community. This article presents the first part of the survey outlining the motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the second part of the survey, we will present a set of techniques to prove upper bounds for dynamic graph problems. In the third part of the survey, we will present a set of techniques to prove lower bounds for dynamic graph problems. A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Though classic problems like coloring, matching, independent set, and many more are extensively studied for static graphs, we are still far from obtaining a complete set of lower bounds and upper bounds results for their dynamic graph counterparts. Along with theoretical advances, the techniques used in dynamic graphs need attention from an implementation perspective. The practical potential of these techniques is yet to be explored. We invite undergraduate researchers and programmers to consider an efficient implementation of these techniques through this three-part survey. The survey can also be used to understand the first algorithms for several recent dynamic graph algorithms.
An Invitation to Dynamic Graph Problems: Lower Bounds — III
In this section of Resonance, we invite readers to pose questions likely to be raised in a classroom situation. We may suggest strategies for dealing with them, or invite responses, or both. “Classroom” is equally a forum for raising broader issues and sharing personal experiences and viewpoints on matters related to teaching and learning science. We present a three-part paper consisting of a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science community. In this third part of the three-part survey paper, we present a set of techniques to prove lower bounds for dynamic graph problems. In the first part1 of the survey, we presented the motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the second part2 of the survey, we presented a set of techniques to prove upper bounds for dynamic graph problems. A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Research in dynamic graphs has succeeded in obtaining efficient upper bounds for an extensive collection of problems. However, there are problems of stubborn nature. Such complex problems lead to the investigation of lower bounds.