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.
Parameterized Complexity of Minimum Membership Dominating Set
Given a graph G= (V, E) and an integer k, the Minimum Membership Dominating Set (MMDS) problem seeks to find a dominating set S⊆ V of G such that for each v∈ V , | N[v] ∩ S| is at most k. We investigate the parameterized complexity of the problem and obtain the following results for the MMDS problem. First, we show that the MMDS problem is NP-hard even on planar bipartite graphs. Next, we show that the MMDS problem is W[1]-hard for the parameter pathwidth (and thus, for treewidth) of the input graph. Then, for split graphs, we show that the MMDS problem is W[2]-hard for the parameter k. Further, we complement the pathwidth lower bound by an FPT algorithm when parameterized by the vertex cover number of input graph. In particular, we design a 2 O(vc)| V| O(1) time algorithm for the MMDS problem where vc is the vertex cover number of the input graph. Finally, we show that the running time lower bound based on ETH is tight for the vertex cover parameter.
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.
Accelerating Computation of Steiner Trees on GPUs
The Steiner Tree Problem (STP) is a well studied graph theoretic problem. It computes a minimum-weighted tree of a given graph such that the tree spans a given subset of vertices called terminals. STP is NP-hard. Due to its wide applicability, it has been a challenge problem in the 11th DIMACS implementation challenge and the PACE 2018 challenge. Due to its importance, polynomial-time approximation algorithms have been devised for solving the STP. One of the most popular algorithms is by Kou, Markowsky and Berman (KMB) which provides a 2-approximation to STP. In practice, a naïve implementation of the KMB algorithm is prohibitively slow for large graphs. Our goal in this work is to improve KMB algorithm’s practical utility by parallelizing it on GPU and reduce its execution time on real-world graphs. This parallelization faces several challenges due to the inherent irregular nature of computation, as well as critical design decisions affecting the algorithm choice and optimizations. We overcome these challenges with interesting algorithmic observations and by exploiting parallelization within sub-steps, and develop the first GPU-based efficient approach to computing Steiner trees using KMB. We illustrate the effectiveness of our approach using several graph benchmarks from the DIMACS Challenge, the PACE Challenge, SteinLib, and SNAP. Our highly optimized GPU implementation achieves an average 20× speedup over the CPU-sequential Open Graph algorithms and Data structure (OGDF)’s KMB implementation. In addition to this, our optimized CPU implementation achieves an average 4× over OGDF’s KMB, the only published open-source KMB implementation.
Parameterized optimization in uncertain graphs-A survey and some results
We present a detailed survey of results and two new results on graphical models of uncertainty and associated optimization problems. We focus on two well-studied models, namely, the Random Failure (RF) model and the Linear Reliability Ordering (LRO) model. We present an FPT algorithm parameterized by the product of treewidth and max-degree for maximizing expected coverage in an uncertain graph under the RF model. We then consider the problem of finding the maximal core in a graph, which is known to be polynomial time solvable. We show that the PROBABILISTIC-CORE problem is polynomial time solvable in uncertain graphs under the LRO model. On the other hand, under the RF model, we show that the PROBABILISTIC-CORE problem is W[1]-hard for the parameter d, where d is the minimum degree of the core. We then design an FPT algorithm for the parameter treewidth.
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.
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.