Abstract: Ivan Bliznets, Marek Cygan, Paweł Komosa, Michał Pilipczuk, Lukáš Mach

In this work, we focus on several completion problems for subclasses of chordal graphs: MINIMUM FILL-IN, INTERVAL COMPLETION, PROPER INTERVAL COMPLETION, TRIVIALLY PERFECT COMPLETION, and THRESHOLD COMPLETION. In these problems, the task is to add at most k edges to a given graph to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds for all these problems, as well as for the related CHAIN COMPLETION problem: • Assuming the Exponential Time Hypothesis, none of these problems can be solved in time 2O(n1/2/logc n) or 2O(k1/4/logc k)· nO(1), for some integer c. • Assuming the non-existence of a subexponential-time approximation scheme for MIN BISECTION on d-regular graphs, for some constant d, none of these problems can be solved in time 2o(n) or 2o√k)}· nO(1). PubDate: Wed, 11 Mar 2020 00:00:00 GMT

Abstract: Paweł Gawrychowski, Shay Mozes, Oren Weimann

We present an optimal data structure for submatrix maximum queries in n× n Monge matrices. Our result is a two-way reduction showing that the problem is equivalent to the classical predecessor problem in a universe of polynomial size. This gives a data structure of O(n) space that answers submatrix maximum queries in O(log log n) time, as well as a matching lower bound, showing that O(log log n) query-time is optimal for any data structure of size O(npolylog(n)). Our result settles the problem, improving on the O(log2 n) query time in SODA’12, and on the O(log n) query-time in ICALP’14. In addition, we show that partial Monge matrices can be handled in the same bounds as full Monge matrices. PubDate: Thu, 05 Mar 2020 00:00:00 GMT

Abstract: Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen, Veli Mäkinen

The field of succinct data structures has flourished over the past 16 years. Starting from the compressed suffix array by Grossi and Vitter (STOC 2000) and the FM-index by Ferragina and Manzini (FOCS 2000), a number of generalizations and applications of string indexes based on the Burrows-Wheeler transform (BWT) have been developed, all taking an amount of space that is close to the input size in bits. In many large-scale applications, the construction of the index and its usage need to be considered as one unit of computation. For example, one can compare two genomes by building a common index for their concatenation and by detecting common substructures by querying the index. PubDate: Thu, 05 Mar 2020 00:00:00 GMT

In this article, we consider the problem of testing whether a graph has bounded arboricity. The class of graphs with bounded arboricity includes many important graph families (e.g., planar graphs and randomly generated preferential attachment graphs). Graphs with bounded arboricity have been studied extensively in the past, particularly because for many problems, they allow for much more efficient algorithms and/or better approximation ratios. We present a tolerant tester in the general-graphs model. The general-graphs model allows access to degree and neighbor queries, and the distance is defined with respect to the actual number of edges. Namely, we say that a graph G is ε-close to having arboricity α if by removing at most an ε-fraction of its edges, we can obtain a graph G′ that has arboricity α, and otherwise we say that G is ε-far. PubDate: Thu, 05 Mar 2020 00:00:00 GMT

Abstract: Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman

The metric Ramsey problem asks for the largest subset S of a metric space that can be embedded into an ultrametric (more generally into a Hilbert space) with a given distortion. Study of this problem was motivated as a non-linear version of Dvoretzky theorem. Mendel and Naor [29] devised the so-called Ramsey Partitions to address this problem, and showed the algorithmic applications of their techniques to approximate distance oracles and ranking problems. In this article, we study the natural extension of the metric Ramsey problem to graphs, and introduce the notion of Ramsey Spanning Trees. We ask for the largest subset S ⊆ V of a given graph G=(V, E), such that there exists a spanning tree of G that has small stretch for S. PubDate: Thu, 05 Mar 2020 00:00:00 GMT

Abstract: Saleh Soltan, Mihalis Yannakakis, Gil Zussman

We introduce and study the doubly balanced connected graph partitioning problem: Let G=(V, E) be a connected graph with a weight (supply/demand) function p : V → {−1, +1} satisfying p(V)=∑ j&isin V p(j) = 0. The objective is to partition G into (V1,V2) such that G[V1] and G[V2] are connected, ∣p(V1)∣,∣p(V2)∣≤ cp, and max{ &frac;∣V1∣∣V2∣,&frac;∣V2∣∣V1∣} ≤ cs, for some constants cp and cs. When G is 2-connected, we show that a solution with cp=1 and cs=2 always exists and can be found in randomized polynomial time. Moreover, when G is 3-connected, we show that there is always a “perfect” solution (a partition with p(V1)=p(V2)=0 and ∣V1∣=∣V2∣, if ∣V∣≡ 0 (mod 4)), and it can be found in randomized polynomial time. PubDate: Thu, 05 Mar 2020 00:00:00 GMT

Abstract: Fedor V. Fomin, Daniel Lokshtanov, Sudeshna Kolay, Fahad Panolan, Saket Saurabh

A rectilinear Steiner tree for a set K of points in the plane is a tree that connects k using horizontal and vertical lines. In the Rectilinear Steiner Tree problem, the input is a set K={z1,z2,…, zn} of n points in the Euclidean plane (R2), and the goal is to find a rectilinear Steiner tree for k of smallest possible total length. A rectilinear Steiner arborescence for a set k of points and a root r ∈ K is a rectilinear Steiner tree T for K such that the path in T from r to any point z ∈ K is a shortest path. PubDate: Thu, 05 Mar 2020 00:00:00 GMT

Abstract: Maria-Florina Balcan, Nika Haghtalab, Colin White

The k-center problem is a canonical and long-studied facility location and clustering problem with many applications in both its symmetric and asymmetric forms. Both versions of the problem have tight approximation factors on worst case instances: a 2-approximation for symmetric k-center and an O(log*(k))-approximation for the asymmetric version. Therefore, to improve on these ratios, one must go beyond the worst case. In this work, we take this approach and provide strong positive results both for the asymmetric and symmetric k-center problems under a natural input stability (promise) condition called α-perturbation resilience [15], which states that the optimal solution does not change under any α-factor perturbation to the input distances. PubDate: Thu, 05 Mar 2020 00:00:00 GMT

We construct a theory of holant clones to capture the notion of expressibility in the holant framework. Their role is analogous to the role played by functional clones in the study of weighted counting Constraint Satisfaction Problems. We explore the landscape of conservative holant clones and determine the situations in which a set F of functions is “universal in the conservative case,” which means that all functions are contained in the holant clone generated by F together with all unary functions. When F is not universal in the conservative case, we give concise generating sets for the clone. We demonstrate the usefulness of the holant clone theory by using it to give a complete complexity-theory classification for the problem of approximating the solution to conservative holant problems. PubDate: Thu, 05 Mar 2020 00:00:00 GMT

We present a unified (randomized) polynomial-time approximation scheme (PTAS) for the prize collecting traveling salesman problem (PCTSP) and the prize collecting Steiner tree problem (PCSTP) in doubling metrics. Given a metric space and a penalty function on a subset of points known as terminals, a solution is a subgraph on points in the metric space whose cost is the weight of its edges plus the penalty due to terminals not covered by the subgraph. Under our unified framework, the solution subgraph needs to be Eulerian for PCTSP, while it needs to be a tree for PCSTP. Before our work, even a QPTAS for the problems in doubling metrics is not known. PubDate: Thu, 05 Mar 2020 00:00:00 GMT

Abstract: Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein

We consider the problem of maintaining a maximal independent set in a dynamic graph subject to edge insertions and deletions. Recently, Assadi et al. (at STOC’18) showed that a maximal independent set can be maintained in sublinear (in the dynamically changing number of edges) amortized update time. In this article, we significantly improve the update time for uniformly sparse graphs. Specifically, for graphs with arboricity α, the amortized update time of our algorithm is O(α2 ṡ log2 n), where n is the number of vertices. For low arboricity graphs, which include, for example, minor-free graphs and some classes of “real-world” graphs, our update time is polylogarithmic. PubDate: Thu, 05 Mar 2020 00:00:00 GMT