Abstract: Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, Meirav Zehavi

We consider four well-studied NP-complete packing/covering problems on graphs: Feedback Vertex Set in Tournaments (FVST), Cluster Vertex Deletion (CVD), Triangle Packing in Tournaments (TPT) and Induced P3-Packing. For these four problems, kernels with O(k2) 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 article, we give the first kernels for FVST, CVD, TPT, and Induced P3-Packing with a subquadratic number of vertices. PubDate: Tue, 08 Jan 2019 00:00:00 GMT

Abstract: Marek Cygan, Marcin Mucha, Karol Węgrzycki, Michał Włodarczyk

In recent years, significant progress has been made in explaining the apparent hardness of improving upon the naive solutions for many fundamental polynomially solvable problems. This progress has come in the form of conditional lower bounds—reductions from a problem assumed to be hard. The hard problems include 3SUM, All-Pairs Shortest Path, SAT, Orthogonal Vectors, and others. In the (min ,+)-convolution problem, the goal is to compute a sequence (c[i])n−1i=0, where c[k] = mini=0,&ldots; ,k { a[i] + b[k−i]}, given sequences (a[i])n−1i=0 and (b[i])n−1i=0. This can easily be done in O(n2) time, but no O(n2−ϵ) algorithm is known for ϵ> 0. PubDate: Tue, 08 Jan 2019 00:00:00 GMT

In this article, we develop an O((m log k)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 MSF(n′,m′,γ) denotes the time complexity of solving the maximum submodular flow problem in a network with n′ nodes, m′ edges, and the complexity γ 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 n3 log k) time. This is the first combinatorial strongly polynomial time algorithm for this problem. PubDate: Thu, 20 Dec 2018 00:00:00 GMT

Abstract: Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, Ryan Williams

Properties definable in first-order logic are algorithmically interesting for both theoretical and pragmatic reasons. Many of the most studied algorithmic problems, such as Hitting Set and Orthogonal Vectors, are first-order, and the first-order properties naturally arise as relational database queries. A relatively straightforward algorithm for evaluating a property with k+1 quantifiers takes time O(mk) and, assuming the Strong Exponential Time Hypothesis (SETH), some such properties require O(mk−ε) time for any ε> 0. (Here,>m represents the size of the input structure, i.e., the number of tuples in all relations.) We give algorithms for every first-order property that improves this upper bound to mk/2Θ (√ log n), i.e., an improvement by a factor more than any poly-log, but less than the polynomial required to refute SETH. PubDate: Tue, 18 Dec 2018 00:00:00 GMT

Given a graph G and a parameter k, the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset U⊆ V(G) of size at most k that hits all induced cycles of size at least 4. The existence of a polynomial kernel for 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 CVD of size O (k161 log58k) and asked whether one can design a kernel of size O (k10) [Jansen an Pilipczuk, SODA 2017]. While we do not completely resolve this question, we design a significantly smaller kernel of size O (k12 log10k), inspired by the O (k2) -size kernel for Feedback Vertex Set [Thomassé, TALG 2010]. PubDate: Sat, 08 Dec 2018 00:00:00 GMT

We present a simple deterministic single-pass (2+ε)-approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves on the currently best known approximation ratio of (4+ε). Our algorithm uses O(nlog2 n) bits of 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. PubDate: Fri, 07 Dec 2018 00:00:00 GMT

The Weighted Tree Augmentation Problem (WTAP) is a fundamental well-studied problem in the field of network design. Given an undirected tree G=(V,E), an additional set of edges L ⊑ V× V disjoint from E called links and a cost vector c∈ R≥ 0L, WTAP asks to find a minimum-cost set F⊑ L with the property that (V,E∪ F) is 2-edge connected. The special case where cℓ = 1 for all ℓ ∈ L is called the Tree Augmentation Problem (TAP). For the class of bounded cost vectors, we present the first improved approximation algorithm for WTAP in more than three decades. PubDate: Fri, 07 Dec 2018 00:00:00 GMT

Abstract: David Adjiashvili, Andrea Baggio, Rico Zenklusen

The Firefighter problem and a variant of it, known as Resource Minimization for Fire Containment (RMFC), are natural models for optimal inhibition of harmful spreading processes. Despite considerable progress on several fronts, the approximability of these problems is still badly understood. This is the case even when the underlying graph is a tree, which is one of the most-studied graph structures in this context and the focus of this article. In their simplest version, a fire spreads from one fixed vertex step by step from burning to adjacent non-burning vertices, and at each time step B many non-burning vertices can be protected from catching fire. PubDate: Fri, 07 Dec 2018 00:00:00 GMT

In this article, we show how to compute for n-vertex planar graphs in O(n11/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(n15/8 polylog(n)) expected time, we can also compute the number of pairs of vertices at distances smaller than a given threshold. These are the first algorithms for these problems using time O(nc) for some constant c< 2, even when restricted to undirected, unweighted planar graphs. PubDate: Fri, 07 Dec 2018 00:00:00 GMT

Abstract: Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek

The main result of this article 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 Dvořák and Kupec. Using a reduction to even Δ-matroids, we then extend the tractability result to larger classes of Δ-matroids that we call efficiently coverable. It properly includes classes that were known to be tractable before, namely, co-independent, compact, local, linear, and binary, with the following caveat: We represent Δ-matroids by lists of tuples, while the last two use a representation by matrices. PubDate: Fri, 07 Dec 2018 00:00:00 GMT

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. PubDate: Thu, 06 Dec 2018 00:00:00 GMT

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 an input unweighted n-vertex graph with O(n1+1/k) expected edges in O(k) rounds of communication. In this article, we improve the result of Reference [48] by showing a k-round distributed algorithm in the same model that constructs a (2k−1)-spanner with O(n1+1/k}/ε) edges, with probability 1−ε for any ε>0. Moreover, when k=ω(log n), our algorithm produces (still in k rounds) ultra-sparse spanners, i.e., spanners of size n(1+ o(1)), with probability 1−o(1). To our knowledge, this is the first distributed algorithm in the CONGEST or in the PRAM models that constructs spanners or skeletons (i.e., connected spanning subgraphs) that are sparse. PubDate: Fri, 16 Nov 2018 00:00:00 GMT

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 result casts a more favorable light on these algorithms’ exponential worst-case running times. Furthermore, as a consequence of our approach, we obtain several novel hardness results. For example, for a given input to the Simplex Algorithm, deciding whether a given variable ever enters the basis during the algorithm’s execution and determining the number of iterations needed are both NP-hard problems. PubDate: Fri, 16 Nov 2018 00:00:00 GMT

Abstract: Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke

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 page into the cache. At any point in time, the sum of the sizes of the pages stored in the cache cannot exceed k. The input consists of a sequence of page requests. If a page is not present in the cache at the time it is requested, it has to be loaded into the cache, incurring a cost of cp. We give a randomized O(log k)-competitive online algorithm for the generalized caching problem, improving the previous bound of O(log2 k) by Bansal, Buchbinder, and Naor (STOC’08). PubDate: Fri, 16 Nov 2018 00:00:00 GMT

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 problem of how much knowledge the agent has to have a priori, to explore the graph in a given time, using a deterministic algorithm. Following the paradigm of algorithms with advice, this a priori information (advice) is provided to the agent by an oracle, in the form of a binary string, whose length is called the size of advice. PubDate: Fri, 16 Nov 2018 00:00:00 GMT

Abstract: Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi

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 yielded linear-time algorithms on bounded clique-width graphs by a well-known theorem of Courcelle, Makowsky, and Rotics). Each of these problems can be solved in time g(k)nf(k) on graphs of clique-width k. Fomin et al. (2010) showed that the running times cannot be improved to g(k)nO(1) assuming W[1]≠FPT. However, this does not rule out non-trivial improvements to the exponent f(k) in the running times. PubDate: Fri, 16 Nov 2018 00:00:00 GMT

Abstract: Petra Berenbrink, Ralf Klasing, Adrian Kosowski, Frederik Mallmann-Trenn, Przemysław uzna&nstrok;ski

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 undirected network. In every timestep, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the most-loaded and the least-loaded processor as quickly as possible. In this work, we identify some natural conditions on deterministic load-balancing algorithms to improve upon the long-standing results of Rabani et al. (1998). Specifically, we introduce the notion of cumulatively fair load-balancing algorithms where in any interval of consecutive timesteps, the total number of tokens sent out over an edge by a node is the same (up to constants) for all adjacent edges. PubDate: Fri, 16 Nov 2018 00:00:00 GMT

Abstract: Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz

Nowhere dense classes of graphs [21, 22] are very general classes of uniformly sparse graphs with several seemingly unrelated characterisations. From an algorithmic perspective, a characterisation of these classes in terms of uniform quasi-wideness, a concept originating in finite model theory, has proved to be particularly useful. Uniform quasi-wideness is used in many fpt-algorithms on nowhere dense classes. However, the existing constructions showing the equivalence of nowhere denseness and uniform quasi-wideness imply a non-elementary blow up in the parameter dependence of the fpt-algorithms, making them infeasible in practice. As a first main result of this article, we use tools from logic, in particular from a sub-field of model theory known as stability theory, to establish polynomial bounds for the equivalence of nowhere denseness and uniform quasi-wideness. PubDate: Fri, 16 Nov 2018 00:00:00 GMT

We settle the complexity of the Independent Set Reconfiguration problem on bipartite graphs under all three commonly studied reconfiguration models. We show that under the token jumping or token addition/removal model, the problem is NP-complete. For the token sliding model, we show that the problem remains PSPACE-complete. PubDate: Tue, 30 Oct 2018 00:00:00 GMT

Abstract: Arnab Bhattacharyya, Palash Dey, David P. Woodruff

We give the first optimal bounds for returning the ℓ1-heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem. For a stream of m items in { 1, 2, &ldots; , n} and parameters 0 < ϵ < ϕ ⩽ 1, let fi denote the frequency of item i, i.e., the number of times item i occurs in the stream. With arbitrarily large constant probability, our algorithm returns all items i for which fi ⩾ ϕ m, returns no items j for which fj ⩽ (ϕ −ϵ)m, and returns approximations &ftilde;i with |&ftilde;i − fi| ⩽ ϵ m for each item i that it returns. PubDate: Mon, 22 Oct 2018 00:00:00 GMT

Abstract: Zbigniew Gołębiewski, Abram Magner, Wojciech Szpankowski

We continue developing the information theory of structured data. In this article, we study models generating d-ary trees (d ≥ 2) and trees with unrestricted degree. We first compute the entropy which gives us the fundamental lower bound on compression of such trees. Then we present efficient compression algorithms based on arithmetic encoding that achieve the entropy within a constant number of bits. A naïve implementation of these algorithms has a prohibitive time complexity of O(nd) elementary arithmetic operations (each corresponding to a number f(n, d) of bit operations), but our efficient algorithms run in O(n2) of these operations, where n is the number of nodes. PubDate: Mon, 01 Oct 2018 00:00:00 GMT

Abstract: Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie

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 performed, with one-sided error, by an adaptive algorithm that uses Õ(k2)/ε queries (independent of n). Complementing this, our second main result is a lower bound showing that any non-adaptive distribution-free k-junta testing algorithm must make Ω(2k/3) queries even to test to accuracy ε = 1/3. PubDate: Mon, 24 Sep 2018 00:00:00 GMT