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)

## 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)

### In Memoriam: David S. Johnson

http://dl.acm.org/citation.cfm?id=2907073

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.

Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs

We show how to compute for n-vertex planar graphs in O(n^{11/6} polylog(n)) expected time the diameter and the sum of the pairwise distances. The algorithms work for directed graphs with real weights and no negative cycles. In O(n^{15/8} polylog(n)) expected time we can also compute the number of pairs of vertices at distance smaller than a given threshold, These are the first algorithms for these problems using time O(n^c) for some constant c < 2, even when restricted to undirected, unweighted planar graphs.

A (2+µ)-Approximation for Maximum Weight Matching in the Semi-Streaming Model

We present a simple deterministic single-pass (2+µ)-approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves upon the currently best known approximation ratio of (3.5+µ). Our algorithm uses O(n log2 n) space for constant values of µ. It relies on a variation of the local-ratio theorem, which may be of use for other algorithms in the semi-streaming model as well.

Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion

Given a graph $G$ and a parameter $k$, the {\sc Chordal Vertex Deletion (CVD)} problem asks whether there exists a subset $U\subseteq V(G)$ of size at most $k$ that hits all induced cycles of size at least 4. The existence of a polynomial kernel for {\sc CVD} was a well-known open problem in the field of Parameterized Complexity. Recently, Jansen and Pilipczuk resolved this question affirmatively by designing a polynomial kernel for {\sc CVD} of size $\OO(k^{161}\log^{58}k)$, and asked whether one can design a kernel of size $\OO(k^{10})$ [Jansen an Pilipczuk, SODA 2017]. While we do not completely resolve this question, we design a significantly smaller kernel of size $\OO(k^{12}\log^{10} k)$, inspired by the $\OO(k^2)$-size kernel for {\sc Feedback Vertex Set} [Thomass\'{e}, TALG 2010]. Furthermore, we introduce the notion of the independence degree of a vertex, which is our main conceptual contribution.

Common Tangents of Two Disjoint Polygons in Linear Time and Constant Workspace

We provide a remarkably simple algorithm to compute all (at most four) common tangents of two disjoint simple polygons. Given each polygon as a read-only array of its corners in cyclic order, the algorithm runs in linear time and constant workspace and is the first to achieve the two complexity bounds simultaneously. The set of common tangents provides basic information about the convex hulls of the polygonswhether they are nested, overlapping, or disjointand our algorithm thus also decides this relationship.

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.

Even Delta-Matroids and the Complexity of Planar Boolean CSPs

The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even -matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by DvoYák and Kupec. Knowing that edge CSP is tractable for even -matroid constraints allows us to extend the tractability result to a larger class of -matroids that includes many classes that were known to be tractable before, namely co-independent, compact, local and binary.

###### All ACM Journals | See Full Journal Index

Search TALG
enter search term and/or author name