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.
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.
Hybrid genetic algorithm for ridesharing with timing constraints: Efficiency analysis with real-world data
Ridesharing is an effective, affordable and environment-friendly way of transportation. This paper proposes a Hybrid Genetic Algorithm(HGA) using elements from Simulated Annealing(SA) and Local search(LS) which is very suitable for Ridesharing related applications. The designed algorithm efficiently handles advanced constraints like timing windows for pick-up, detour time(or distance), and waiting-time minimization. To quantify the effectiveness of HGA for the Ridesharing problem, we study Ridesharing as a close variant of the Orienteering Problem(OP) and Orienteering Problem with Time Windows(OPTW). Both these problems have been extensively studied and have many benchmark data sets. The experiments performed on popular benchmark instances of orienteering problems show that HGA for orienteering problems outperforms all the available algorithms in the literature. Further, for many of the instances, our HGA has discovered solutions that are better than the current Best Known solutions. Using our HGA for orienteering problems, we have developed a prototype system for Ridesharing. The experiments using real-world New York taxi trip data [19] shows that the system ensures that about 40%-50% of the rides could have been shared, and 60%-70% of customers could have shared rides. The detailed data analysis shows how to tune the parameters for the system to achieve the best possible performance.
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.
Budgeted Dominating Sets in Uncertain Graphs
We study the Budgeted Dominating Set (BDS) problem on uncertain graphs, namely, graphs with a probability distribution p associated with the edges, such that an edge e exists in the graph with probability p(e). The input to the problem consists of a vertex-weighted uncertain graph G = (V,E, p, ω) and an integer budget (or solution size) k, and the objective is to compute a vertex set S of size k that maximizes the expected total domination (or total weight) of vertices in the closed neighborhood of S. We refer to the problem as the Probabilistic Budgeted Dominating Set (PBDS) problem. In this article, we present the following results on the complexity of the PBDS problem. 1. We show that the PBDS problem is NP-complete even when restricted to uncertain trees of diameter at most four. This is in sharp contrast with the well-known fact that the BDS problem is solvable in polynomial time in trees. We further show that PBDS is W[1]-hard for the budget parameter k, and under the Exponential time hypothesis it cannot be solved in no(k) time. 2. We show that if one is willing to settle for (1 ) approximation, then there exists a PTAS for PBDS on trees. Moreover, for the scenario of uniform edge-probabilities, the problem can be solved optimally in polynomial time. 3. We consider the parameterized complexity of the PBDS problem, and show that Uni-PBDS (where all edge probabilities are identical) is W[1]-hard for the parameter pathwidth. On the other hand, we show that it is FPT in the combined parameters of the budget k and the treewidth. 4. Finally, we extend some of our parameterized results to planar and apex-minor-free graphs. Our first hardness proof (Thm. 1) makes use of the new problem of k-Subset ΣΠ Maximization (k-SPM), which we believe is of independent interest. We prove its NP-hardness by a reduction from the well-known k-SUM problem, presenting a close relationship between the two problems.
Effective Parallelization of the Vehicle Routing Problem
Capacitated Vehicle Routing Problem (CVRP) is an important combinatorial optimization problem, which is also NP-hard. A wide array of heuristics have been proposed in the literature to obtain an approximate solution to CVRP. To improve the execution time, parallel methods have been developed for accelerating metaheuristics-based algorithms, genetic algorithms, and evolutionary algorithms for CVRP. Despite these advances, our experiments with the state-of-The-Art parallel solutions indicate that their run times are too high to be practically useful. The combinatorial explosion is so high that the execution time is prohibitively large even on mid-sized CVRP instances having a few hundred customers. In this work, we propose a novel technique which combines local search and randomization for solving CVRP faster with reasonable accuracy, even on large problem instances. Our usage of randomization enables searching a large space of candidate solutions. We experimentally compare our proposed method with the state-of-The-Art GPU implementations on diverse input instances and demonstrate the efficacy of our approach. Our sequential and shared-memory parallel implementations are on an average 36-1189× faster than the state-of-The-Art GPU-parallel genetic algorithms while also achieving a superior solution quality. Furthermore, our reported solutions are close to the current best-known solutions from CVRPLIB.
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.
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 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 about MMDS: 1.W[1]-hardness of the problem parameterized by the pathwidth (and thus, treewidth) of the input graph.2.W[1]-hardness parameterized by k on split graphs.3.An algorithm running in time 2 O(vc)| V| O(1), where vc is the size of a minimum-sized vertex cover of the input graph.4.An ETH-based lower bound showing that the algorithm mentioned in the previous item is optimal.