Abstract: Rezaul A. Chowdhury, Vijaya Ramachandran

We present the buffer heap, a cache-oblivious priority queue that supports Delete-Min, Delete, and a hybrid Insert/Decrease-Key operation in O(1/B log2 N/M) amortized block transfers from main memory, where M and B are the (unknown) cache size and block size, respectively, and N is the number of elements in the queue. We introduce the notion of a slim data structure that captures the situation when only a limited portion of the cache, which we call a slim cache, is available to the data structure to retain data between data structural operations. We show that a buffer heap automatically adapts to such an environment and supports all operations in O(1/λ + 1/B log2 N/λ) amortized block transfers each when the size of the slim cache is λ. PubDate: Wed, 03 Jan 2018 00:00:00 GMT

Abstract: Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos

We give the first linear kernels for the Dominating Set and Connected Dominating Set problems on graphs excluding a fixed graph H as a topological minor. In other words, we prove the existence of polynomial time algorithms that, for a given H-topological-minor-free graph G and a positive integer k, output an H-topological-minor-free graph G′ on O(k) vertices such that G has a (connected) dominating set of size k if and only if G′ has one. Our results extend the known classes of graphs on which the Dominating Set and Connected Dominating Set problems admit linear kernels. Prior to our work, it was known that these problems admit linear kernels on graphs excluding a fixed apex graph H as a minor. PubDate: Wed, 03 Jan 2018 00:00:00 GMT

Abstract: Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh

In the Subset Feedback Vertex Set (Subset FVS) problem, the input is a graph G on n vertices and m edges, a subset of vertices T, referred to as terminals, and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every cycle that contains a terminal. The study of parameterized algorithms for this generalization of the Feedback Vertex Set problem has received significant attention over the past few years. In fact, the parameterized complexity of this problem was open until 2011, when two groups independently showed that the problem is fixed parameter tractable. PubDate: Wed, 03 Jan 2018 00:00:00 GMT

We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in O(m&sqrt;nlog(nN)) time, O(m&sqrt; n) per scale, which matches the running time of the best cardinality matching algorithms on sparse graphs [16, 20, 36, 37]. Here, m,n, and N bound the number of edges, vertices, and magnitude, respectively, of any integer edge weight. Our result improves on a 25-year-old algorithm of Gabow and Tarjan, which runs in O(m&sqrt;nlog nα (m,n) log(nN)) time. PubDate: Wed, 03 Jan 2018 00:00:00 GMT

We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find the shortest tour that visits each of a given collection of subsets (regions or neighborhoods) in the underlying metric space. We give a randomized polynomial-time approximation scheme (PTAS) when the regions are fat weakly disjoint. This notion of regions was first defined when a QPTAS was given for the problem in SODA 2010 (Chan and Elbassioni 2010). The regions are partitioned into a constant number of groups, where in each group, regions should have a common upper bound on their diameters and each region designates one point within it such that these points are far away from one another. PubDate: Wed, 03 Jan 2018 00:00:00 GMT

We consider the problem of online scheduling of jobs on unrelated machines with dynamic speed scaling to minimize the sum of energy and weighted flow-time. We give an algorithm with an almost optimal competitive ratio for arbitrary power functions. (No earlier results handled arbitrary power functions for unrelated machines.) For power functions of the form f(s) = sα for some constant α > 1, we get a competitive ratio of O(α&frac; log α), improving upon a previous competitive ratio of O(α2) by Anand et al. (2012), along with a matching lower bound of Ω(α&frac; log α). Further, in the resource augmentation model, with a 1+ ε speed up, we give a 2(1&frac;ε + 1) competitive algorithm, with essentially the same techniques, improving the bound of 1 + O(1&frac;ε2) by Gupta et al. PubDate: Mon, 18 Dec 2017 00:00:00 GMT

We consider the problem of constructing fast and small binary adder circuits. Among widely used adders, the Kogge-Stone adder is often considered the fastest, because it computes the carry bits for two n-bit numbers (where n is a power of two) with a depth of 2 log2n logic gates, size 4 nlog2n, and all fan-outs bounded by two. Fan-outs of more than two are disadvantageous in practice, because they lead to the insertion of repeaters for repowering the signal and additional depth in the physical implementation. However, the depth bound of the Kogge-Stone adder is off by a factor of two from the lower bound of log2n. PubDate: Thu, 14 Dec 2017 00:00:00 GMT

We define the parametric closure problem, in which the input is a partially ordered set whose elements have linearly varying weights and the goal is to compute the sequence of minimum-weight downsets of the partial order as the weights vary. We give polynomial time solutions to many important special cases of this problem including semiorders, reachability orders of bounded-treewidth graphs, partial orders of bounded width, and series-parallel partial orders. Our result for series-parallel orders provides a significant generalization of a previous result of Carlson and Eppstein on bicriterion subtree problems. PubDate: Wed, 06 Dec 2017 00:00:00 GMT

Abstract: Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan Van Leeuwen

In the Maximum Weight Independent Set problem, the input is a graph G, every vertex has a non-negative integer weight, and the task is to find a set S of pairwise nonadjacent vertices, maximizing the total weight of the vertices in S. We give an nO(log2 n) time algorithm for this problem on graphs excluding the path P6 on 6 vertices as an induced subgraph. Currently, there is no constant k known for which Maximum Weight Independent Set on Pk-free graphs becomes NP-hard, and our result implies that if such a k exists, then k > 6 unless all problems in NP can be decided in quasi-polynomial time. PubDate: Wed, 06 Dec 2017 00:00:00 GMT