ACM Transactions on

Algorithms (TALG)

Latest Articles

Distribution-free Junta Testing

We study the problem of testing whether an unknown n-variable Boolean function is a k-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over {0,1}n. Our first main result is that distribution-free k-junta testing can be... (more)

An Optimal Algorithm for ℓ1-Heavy Hitters in Insertion Streams and Related Problems

We give the first optimal bounds for returning the ℓ1-heavy hitters in a data stream of... (more)

Entropy and Optimal Compression of Some General Plane Trees

We continue developing the information theory of structured data. In this article, we study models generating d-ary trees (d ≥ 2) and trees with... (more)

Efficient Algorithms for Constructing Very Sparse Spanners and Emulators

Miller et al. [48] devised a distributed1 algorithm in the CONGEST model that, given a parameter k = 1,2,&ldots;, constructs an O(k)-spanner of... (more)

The Simplex Algorithm Is NP-Mighty

We show that the Simplex Method, the Network Simplex Method—both with Dantzig’s original pivot rule—and the Successive Shortest Path Algorithm are NP-mighty. That is, each of these algorithms can be used to solve, with polynomial overhead, any problem in NP implicitly during the algorithm’s execution. This... (more)

An O(log k)-Competitive Algorithm for Generalized Caching

In the generalized caching problem, we have a set of pages and a cache of size k. Each page p has a size wp≥ 1 and fetching cost cp for loading the... (more)

The Complexity of Independent Set Reconfiguration on Bipartite Graphs

We settle the complexity of the Independent Set Reconfiguration problem on bipartite graphs under all three commonly studied reconfiguration models.... (more)

Deterministic Graph Exploration with Advice

We consider the fundamental task of graph exploration. An n-node graph has unlabeled nodes, and all ports at any node of degree d are arbitrarily numbered 0,…, d−1. A mobile agent, initially situated at some starting node v, has to visit all nodes and stop. The time of the exploration is the number of edge traversals. We consider the... (more)

Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring

MAX-CUT, EDGE DOMINATING SET, GRAPH COLORING, and HAMILTONIAN CYCLE on graphs of bounded clique-width have received significant attention as they can be formulated in MSO2 (and, therefore, have linear-time algorithms on bounded treewidth graphs by the celebrated Courcelle’s theorem), but cannot be formulated in MSO1 (which would have... (more)

Improved Analysis of Deterministic Load-Balancing Schemes

We consider the problem of deterministic load balancing of tokens in the discrete model. A set of n processors is connected into a d-regular... (more)


In Memoriam: David S. Johnson

About TALG

The ACM Transactions on Algorithms (TALG) publishes original research of the highest quality dealing with algorithms that are inherently discrete and finite, and having mathematical content in a natural way, either in the objective or in the analysis.

read more
On problems equivalent to (min,+)-convolution

In the recent years, significant progress has been made in explaining apparent hardness of improving over naive solutions for many fundamental polynomially solvable problems. This came in the form of conditional lower bounds -- reductions from a problem assumed to be hard. These include 3SUM, All-Pairs Shortest Paths, SAT and Orthogonal Vectors, and others. In the $(\min,+)$-convolution problem, the goal is to compute a sequence $(c[i])^{n-1}_{i=0}$, where $c[k] = $ $\min_{i=0,\ldots,k} $ $\{a[i] $ $+$ $b[k-i]\}$, given sequences $(a[i])^{n-1}_{i=0}$ and $(b[i])_{i=0}^{n-1}$. This can easily be done in $O(n^2)$ time, but no $O(n^{2-\varepsilon})$ algorithm is known for $\varepsilon > 0$. In this paper we undertake a systematic study of the $(\min,+)$-convolution problem as a hardness assumption. As the first step, we establish equivalence of this problem to a group of other problems, including variants of the classic knapsack problem and problems related to subadditive sequences. The $(\min,+)$-convolution has been used as a building block in algorithms for many problems, notably problems in stringology. It has also already appeared as an ad hoc hardness assumption. We investigate some of these connections and provide new reductions and other results. We also explain why replacing this assumption with SETH might not be possible for some problems.

Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems

We consider four well-studied NP-complete packing/covering problems on graphs: Feed- back Vertex Set in Tournaments (FVST), Cluster Vertex Deletion (CVD), Triangle Packing in Tournaments (TPT) and Induced P_3-Packing. For these four problems kernels with O(k^2) vertices have been known for a long time. In fact, such kernels can be obtained by interpreting these problems as finding either a packing of k pairwise disjoint sets of size 3 (3-Set Packing) or a hitting set of size at most k for a family of sets of size at most 3 (3-Hitting Set). In this paper, we give the first kernels for FVST, CVD, TPT and Induced P_3-Packing with a subquadratic number of vertices. Specifically, we obtain the following results. (a) FVST admits a kernel with O(k^1.5 ) vertices. (b) CVD admits a kernel with O(k^(5/3)) vertices. (c) TPT admits a kernel with O(k^(1.5) ) vertices. (d) Induced P_3-Packing admits a kernel with O(k^(5/3 ) vertices. Our results resolve an open problem from WorKer 2010 on the existence of kernels with O(k^(2-e)) vertices for FVST and CVD. All of our results are based on novel uses of old and new expansion lemmas, and a weak form of crown decomposition where (i) almost all of the head is used by the solution (as opposed to all), (ii) almost none of the crown is used by the solution (as opposed to none), and (iii) if H is removed from G, then there is almost no interaction between the head and the rest (as oppose

A dual descent algorithm for node-capacitated multiflow problems and its applications

In this paper, we develop an $O((m \log k) {\rm MSF} (n,m,1))$-time algorithm to find a half-integral node-capacitated multiflow of the maximum total flow-value in a network with $n$ nodes, $m$ edges, and $k$ terminals, where ${\rm MSF} (n',m',\gamma)$ denotes the time complexity of solving the maximum submodular flow problem in a network with $n'$ edges, $m'$ edges, and the complexity $\gamma$ of computing the exchange capacity of the submodular function describing the problem. % By using Fujishige-Zhang algorithm for submodular flow, we can find a maximum half-integral multiflow in $O(m n^3 \log k)$ time. This is the first combinatorial strongly polynomial time algorithm for this problem. % Our algorithm is designed on the basis of a developing theory of discrete convex functions on certain graph structures. % Applications include ``ellipsoid-free" combinatorial implementations of a 2-approximation algorithm for the minimum node-multiway cut problem by Garg, Vazirani, and Yannakakis.

All ACM Journals | See Full Journal Index

Search TALG
enter search term and/or author name