Genome variation graphs are natural candidates to represent a pangenome collection. In such graphs, common subsequences are encoded as vertices and the genomic variations are captured by introducing additional labeled vertices and directed edges. Unlike a linear reference, a reference graph allows a rich representation of the genomic diversities and avoids reference bias. We address the fundamental problem of mapping reads to genome variation graphs. We give a novel mapping algorithm V-MAP for efficient identification of small subgraph of the genome graph for optimal gapped alignment of the read. V-MAP creates space efficient index using locality sensitive minimizer signatures computed using a novel graph winnowing and graph embedding onto metric space for fast and accurate mapping. Experiments involving graph constructed from the 1000 Genomes data and using both real and simulated reads show that V-MAP is fast, memory efficient and can map short reads, as well as PacBio/Nanopore long reads with high accuracy. V-MAP performance was significantly better than the state-of-the-art, especially for long reads.

For a graph $H$, the $H$-free Edge Deletion problem asks whether there exist at most $k$ edges whose deletion from the input graph $G$ results in a graph without any induced copy of $H$. $H$-free Edge Completion and $H$-free Edge Editing are defined similarly where only completion (addition) of edges are allowed in the former and both completion and deletion are allowed in the latter. We completely settle the classical complexities of these problems by proving that $H$-free Edge Deletion is NP-complete if and only if $H$ is a graph with at least two edges, $H$-free Edge Completion is NP-complete if and only if $H$ is a graph with at least two nonedges, and $H$-free Edge Editing is NP-complete if and only if $H$ is a graph with at least three vertices. Our result on $H$-free Edge Editing resolves a conjecture by Alon and Stav [Theoret. Comput. Sci., 2009, pp. 4920--4927]. Additionally, we prove that these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time $2^{o(k)}\cdot |G|^{O(1)}$, unless the exponential time hypothesis fails. Furthermore, we obtain implications on the incompressibility and the inapproximability of these problems.

A diamond is a graph obtained by removing an edge from a complete graph on four vertices. A graph is diamond-free if it does not contain an induced diamond. The Diamond-free Edge Deletion problem asks to find whether there exist at most k edges in the input graph whose deletion results in a diamond-free graph. The problem was proved to be NP-complete and a polynomial kernel of O(k^4) vertices was found by Fellows et. al. (Discrete Optimization, 2011). In this paper, we give an improved kernel of O(k^3) vertices for Diamond-free Edge Deletion. We give an alternative proof of the NP-completeness of the problem and observe that it cannot be solved in time 2^{o(k)} * n^{O(1)}, unless the Exponential Time Hypothesis fails.

Graphics Processing Units (GPUs) have evolved over the years from being graphics accelerator to scalable coprocessor. We implement an algebraic multigrid solver for three dimensional unstructured grids using GPU. Such a solver has extensive applications in Computational Fluid Dynamics (CFD). Using a combination of vertex coloring, optimized memory representations, multi-grid and improved coarsening techniques, we obtain considerable speedup in our parallel implementation. Our solver provides significant acceleration for solving pressure Poisson equations, which is the most time consuming part while solving Navier-Stokes equations. In our experimental study, we solve pressure Poisson equations for flow over lid driven cavity and for laminar flow past square cylinder. Our implementation achieves 915 times speed up for the lid driven cavity problem on a grid of size 2.6 million and a speed up of 1020 times for the laminar flow past square cylinder problem on a grid of size 1.7 million, compared to serial non-multigrid implementations. For our implementation, we used NVIDIA's CUDA programming model.

Consider the classical online scheduling problem where jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by β times the size of thearriving job. Our main result is a linear time ‘online approximation scheme’, that is, a family of online algorithms with competitive ratio 1+ ε and constant migration factor β ( ε ), for any fixed ε > 0. This result is of particular importance if considered in the context of sensitivity analysis: While a newly arriving job may force a complete change of the entire structure of an optimal schedule, only very limited ‘local’ changes suffice to preserve near-optimal solutions. We believe that this concept will find wide application in its own right. We also present simple deterministic online algorithms with migration factors β =2 and β =4/3, respectively. Their competitive ratio 3/2 beats the lower bound on the performance of any online algorithm in the classical setting without migration. We also present improved algorithms and similar results for closely related problems. In particular, there is a short discussion of corresponding results for the objective to maximize the minimum load of a machine. The latter problem has an application for configuring storage servers that was the original motivation for this work. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.