SWAT 2012

Abstract. Understanding complex disease is one of today’s grand challenges. In spite of the rapid advance of biotechnology, disease understanding is still very limited and further computational tools for disease-related data analysis are in dire need. In this talk I will describe some of the approaches that we are developing for these challenges. I will describe methods for utilizing expression profiles of sick and healthy individuals to identify pathways dysregulated in the disease, methods for integrated analysis for expression and protein interactions, and methods for regulatory motif discovery. If time allows, I’ll discuss methods for analysis of genome aberrations in cancer. The utility of the methods will be demonstrated on biological examples.

Abstract. The wavelet tree is a versatile data structure that serves a number of purposes, from string processing to geometry and more. It can be regarded as a device that represents a sequence, or that represents a grid of points, or that encodes a reordering of a sequence of elements. In addition, its space adapts to various compressibility criteria of the the data it encodes, enabling compressed representations. New competitive solutions to fundamental problems, based on wavelet trees, are appearing every year. In this talk I will give an overview of the surprising number of applications in which I have found wavelet trees extremely useful: basic and weighted point grids, sets of rectangles, strings, permutations, binary relations, graphs, inverted indexes, document retrieval indexes, full-text indexes, XML indexes, and general numeric sequences.

Abstract. The watchman route problem is a classic optimization problem in computational geometry: Determine a shortest path/tour for an observer to be able to view all points within a given geometric domain. The problem combines aspects of the traveling salesperson problem and the set cover problem. While some special cases have polynomial-time exact solutions, most versions of the problem are NP-hard, so attention focuses on approximation algorithms. The problem comes in many varieties, depending on the nature of the domain being searched, assumptions about the searcher(s), and the objective function. We briefly survey the research area of visibility coverage tours and describe some recent advances in approximation algorithms.

Abstract. The title of my presentation is a motto originally coined in urban design about 100 years ago, but used in various different contexts since. The motto can also be applied to many areas in computer science. For instance, in computational game theory, each agent tries to maximize his/her own (local) benefit, and we analyze the (global) social welfare. Also, computer architecture is designed for locality of reference. Recently, the distributed computing community has made tremendous progress towards understanding the complexity of distributed message passing algorithms. In networks, a rich selection of upper and lower bounds regarding how much time it takes to solve or approximate a problem have been established; we now have a good understanding how local actions and global goal influence each other. This distributed complexity theory may ultimately help to give the "think global, act local" motto a mathematical foundation. In my talk I will introduce the message passing model, present a few selected results, mention prominent open problems, and discuss some of the most exciting future research directions. Upcoming applications may not necessarily lie in computer science but rather in other areas that deal with networked systems, e.g. biology or social sciences.

A new class of visibility problems based on the notion of α-visibility is introduced. A segment t in a polygonal scene S is said to be α-visible from a point p, if and only if there exists a triangle pab such that (a) the angle at p equals α, (b) the segment ab ⊆ t, and (c) the triangle pab does not intersect any object of S in its interior, i.e., triangle pab is empty.

In this model of visibility, we study the classical variants of point visibility, weak and complete segment visibility, and the construction of the visibility graph. We also investigate the natural query versions of these problems and problem instances in which α is either fixed or specified at the query time.

Computing the Fréchet distance for surfaces is a surprisingly hard problem. We introduce a partial variant of the Fréchet distance problem, which for given surfaces P and Q asks to compute a surface R in Q with minimum Fréchet distance to P. Like the Fréchet distance, the partial Fréchet distance is NP-hard to compute between terrains and also between polygons with holes. We restrict P, Q, and R to be coplanar simple polygons. For this restricted class of surfaces, we develop a polynomial time algorithm to compute the partial Fréchet distance and show that such an R in Q can be computed in polynomial time as well. This is the first algorithm to address a partial Fréchet distance problem for surfaces. The two main ingredients are Buchin et al.'s algorithm for computing the Fréchet distance between simple polygons and Godau's constrained embedding problem for planar graphs which is NP-hard in general.

We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and the best approximation ratio by van Leeuwen (2009) before our work was 2. The algorithm exploits the shifting strategy of Hochbaum and Maass (1985), and a novel use of dynamic programming to solve the instances in which the points are constrained to lie in a constant-height region. The scheme can be generalized to the budgeted unique unit-square coverage problem, in which each point has a profit, each square has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound.

Given a set L of non-parallel lines, a watchman route for L is a closed curve contained in the union of the lines in L such that every point on any line is visible (along a line) from at least one point of the route; similarly, we define a watchman route for a connected set S of line segments. The watchman route problem for a given set of lines or line segments is to find a shortest watchman route for the input set, and these problems are natural special cases of the watchman route problem in multiply connected polygonal domains.

In this paper, we show that the problem of computing a shortest watchman route for a set of n non-parallel lines in the plane is polynomially tractable, while it becomes NP-hard in 3D. Then, we reprove NP-hardness of this problem for line segments in the plane and provide a polynomial-time approximation algorithm with ratio O(log³ n). Additionally, we consider some special cases of the watchman route problem on line segments, for which we are able to provide improved approximation or exact algorithms.

We investigate higher-order Voronoi diagrams in the city metric. This metric is induced by quickest paths in the L₁ metric in the presence of an accelerating transportation network of axis-parallel line segments. For the structural complexity of kth-order city Voronoi diagrams of n point sites, we show an upper bound of O(k(n − k) + kc) and a lower bound of Ω(n + kc), where c is the complexity of the transportation network. This is quite different from the bound O(k(n − k)) in the Euclidean metric. For the special case where k = n − 1 the complexity in the Euclidean metric is O(n), while that in the city metric is Θ(nc).

Furthermore, we develop an O(k²(n + c) log n)-time iterative algorithm to compute the kth-order city Voronoi diagram and an O(nc log²(n + c) log n)-time divide-and-conquer algorithm to compute the farthest-site city Voronoi diagram.

We construct a new proximity graph, called the Pie Delaunay graph, on a set of n points which is a super graph of YG and Euclidean minimum spanning tree (EMST). We efficiently maintain the PDG where the points are moving in the plane. We use the kinetic PDG to create a kinetic data structure (KDS) for maintenance of the YG and the EMST on a set of n moving points in 2-dimensional space. Assuming x and y coordinates of the points are defined by algebraic functions of at most degree s, the structure uses O(n) space, O(n log n) preprocessing time, and processes O(n²λ_2s+2(sn) β_s+2(n)) events for the YG and O(n²λ_2s+2(sn)) events for the EMST, each in O(log² n) time. Here, λ_s(n) = nβ_s(n) is the maximum length of Davenport-Schinzel sequences of order s on n symbols.

Our KDS processes nearly cubic events for the EMST which improves the previous bound O(n⁴) by Rahmati et al.

Given a metric (V, d) and an integer k, we consider the problem of covering the points of V with at most k clusters so as to minimize the sum of radii or the sum of diameters of these clusters. The former problem is called the Minimum Sum Radii (MSR) and the latter is the Minimum Sum Diameters (MSD) problems. The current best polynomial time algorithms for these problems have approximation ratios 3.504 and 7.008, respectively [Charikar–Panigrahy, JCSS 2004]. For the MSR problem, we give an exact algorithm for when the metric is the shortest-path metric of an unweighted graph and there cannot be any singleton clusters. This exact algorithm is based on some structural properties of an optimal solution. For the MSD problem on the plane with Euclidean distances, we present a polynomial time approximation scheme. The previously best known approximation algorithm for MSD on the plane has ratio 2.

The problem of finding a nearest neighbor from a set of points in R^d to a complex query object has attracted considerable attention due to various applications in computational geometry, bio-informatics, information retrieval, etc. We propose a generic method that solves the problem for various classes of query objects and distance functions in a unified way. Moreover, for linear space requirements the method simplifies the known approach based on ray-shooting in the lower envelope of an arrangement.

In the Connected Vertex Cover problem we are given an undirected graph G together with an integer k and we are to find a subset of vertices X of size at most k, such that X contains at least one end-point of each edge and moreover X induces a connected subgraph. For this problem we present a deterministic algorithm running in O(2^k n^O(1)) time and polynomial space, improving over previously best O(2.4882^k n^O(1)) deterministic algorithm and O(2^k n^O(1)) randomized algorithm. Furthermore, when usage of exponential space is allowed, we present an O(2^k k(n + m)) time algorithm that solves a more general variant with arbitrary real weights.

Finally, we show that in O(2^k k(n + m)) time and O(2^k k) space one can count the number of connected vertex covers of size at most k, which can not be improved to O((2 − ε)^k n^O(1)) for any ε > 0 under the Strong Exponential Time Hypothesis, as shown by Cygan et al. [CCC’12].

An undirected graph is said to be split if its vertex set can be partitioned into two sets such that the subgraph induced on one of them is a complete graph and the subgraph induced on the other is an independent set. We study the problem of deleting the minimum number of vertices or edges from a given input graph so that the resulting graph is split. The problem is well known to be NP-Complete from a classical result of Lewis and Yannakakis (JCSS 1980). We address the problem in the parameterized complexity framework.

As this graph class has a finite number of forbidden sets, the problem is known to be fixed-parameter tractable by a general result of Cai (IPL 1996). However, unlike the closely related class of Chordal graphs, deletion problems related to split graphs aren't well studied. We initiate a systematic study and give efficient fixed-parameter algorithms and polynomial sized kernels for the problem. More precisely,

1. for Split Vertex Deletion, the problem of determining whether there are k vertices whose deletion results in a split graph, we give an O*(2^k) algorithm improving on the previous best bound of O*(2.32^k). We also give an (the first, to our knowledge) O(k³)-sized kernel for the problem.
2. For Split Edge Deletion, the problem of determining whether there are k edges whose deletion results in a split graph, we give an O*(2^√k log k) algorithm, which is the first subexponential time algorithm for the problem. We also prove the existence of a O(k²) vertex kernel, improving upon the existing O(k⁴) vertex kernel (Guo 2007). These results also extend to the problem of determining if we can add at most k edges to the given graph to make it split.

We obtain our algorithms by proving some interesting structural properties of split graphs, which can be of independent interest. In addition, we note that our algorithm for Split Edge Deletion adds to the small number of subexponential parameterized algorithms not obtained through bidimensionality, and in general graphs.

Given an input graph G and an integer k, the parameterized K₄-minor cover problem asks whether there is a set S of at most k vertices whose deletion results in a K₄-minor-free graph, or equivalently in a graph of treewidth at most 2. This problem is inspired by two well-studied parameterized vertex deletion problems, Vertex Cover and Feedback Vertex Set, which can also be expressed as Treewidth-t Vertex Deletion problems: t = 0 for Vertex Cover and t = 1 for Feedback Vertex Set.

While a single-exponential FPT algorithm has been known for a long time for Vertex Cover, such an algorithm for Feedback Vertex Set was devised comparatively recently. While it is known to be unlikely that Treewidth-t Vertex Deletion can be solved in time c^o(k) ∙ n^O(1), it was open whether the K₄-minor cover could be solved in single-exponential FPT time, i.e. in c^k ∙ n^O(1) time for some constant c. This paper answers this question in the affirmative.

We present an O(n³ log log n / log² n) time algorithm for all pairs shortest paths. This algorithm improves on the best previous result of O(n³ (log log n)³ / log² n) time.

The biclique problem asks, given a graph G and a parameter k, whether G has a complete bipartite subgraph of k vertices in each part (a biclique of order k). Fixed-parameter tractability of this problem is a longstanding open question in parameterized complexity that received a lot of attention from the community. In this paper we consider a restricted version of this problem by introducing an additional parameter s and assuming that G does not have induced (i.e. chordless) paths of length s.

We prove that under this parameterization the problem becomes fixed-parameter linear. The main tool in our proof is a Ramsey-type theorem stating that a graph with a long (not necessarily induced) path contains either a long induced path or a large biclique.

Paths P₁, …, P_k in a graph G = (V, E) are said to be mutually induced if for any 1 ≤ i < j ≤ k, P_i and P_j have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to test whether a graph G with k pairs of specified vertices (s_i, t_i) contains k mutually induced paths P_i such that P_i connects s_i and t_i for i = 1, …, k. This problem is known to be NP-complete already for k = 2. We prove that it can be solved in polynomial time for AT-free graphs even when k is part of the input. As a consequence, the problem of testing whether a given AT-free graph contains some graph H as an induced topological minor admits a polynomial-time algorithm, as long as H is fixed; we show that such an algorithm is essentially optimal by proving that the problem is W[1]-hard, even on a subclass of AT-free graphs, namely cobipartite graphs, when parameterized by |V_H|. We also show that the problems k-in-a-Path and k-in-a-Tree can be solved in polynomial time, even when k is part of the input. These problems are to test whether a graph contains an induced path or induced tree, respectively, spanning k given vertices.

In the final paper of the Graph Minors series [Neil Robertson and Paul D. Seymour. Graph Minors XXIII. Nash-Williams' immersion conjecture, J. Comb. Theory, Ser. B, 100(2):181–205, 2010.], N. Robertson and P. Seymour proved that graphs are well-quasi-ordered with respect to the immersion relation. A direct implication of this theorem is that each class of graphs that is closed under taking immersions can be fully characterized by forbidding a finite set of graphs (immersion obstruction set). However, as the proof of the well-quasi-ordering theorem is non-constructive, there is no generic procedure for computing such a set. Moreover, it remains an open issue to identify for which immersion-closed graph classes the computation of those sets can become effective. By adapting the tools that where introduced in [Isolde Adler, Martin Grohe and Stephan Kreutzer. Computing excluded minors, SODA, 2008: 641–650.] for the effective computation of obstruction sets for the minor relation, we expand the horizon of the computability of obstruction sets for immersion-closed graph classes. In particular, we prove that there exists an algorithm that, given the immersion obstruction sets of two graph classes that are closed under taking immersions, outputs the immersion obstruction set of their union.

In this paper, we study the problem of moving n sensors on a line to form a barrier coverage of a specified segment of the line such that the maximum moving distance of the sensors is minimized. Previously, it was an open question whether this problem on sensors with arbitrary sensing ranges is solvable in polynomial time. We settle this open question positively by giving an O(n² log n log log n) time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes O(n²) time. We present an O(n log n) time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes O(n) time. Also, we extend our techniques to the cycle version of the problem where the barrier coverage is for a simple cycle and the sensors are allowed to move only along the cycle. For sensors with the same-size sensing range, we solve the cycle version in O(n) time.

Let K be a simplicial complex and g the rank of its p-th homology group H_p(K) defined with Z₂ coefficients. We show that we can compute a basis H of H_p(K) and annotate each p-simplex of K with a binary vector of length g with the following property: the annotations, summed over all p-simplices in any p-cycle z, provide the coordinate vector of the homology class [z] in the basis H. The basis and the annotations for all simplices can be computed in O(n^ω) time, where n is the size of K and ω < 2.376 is a quantity so that two n × n matrices can be multiplied in O(n^ω) time. The pre-computation of annotations permits answering queries about the independence or the triviality of p-cycles efficiently.

Using annotations of edges in 2-complexes, we derive better algorithms for computing optimal basis and optimal homologous cycles in 1-dimensional homology. Specifically, for computing an optimal basis of H₁(K), we improve the time complexity known for the problem from O(n⁴) to O(n^ω + n²g^ω−1). Here n denotes the size of the 2-skeleton of K and g the rank of H₁(K). Computing an optimal cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm taking O(2^O(g)n log n) time is known for surfaces. We extend this algorithm to work with arbitrary 2-complexes in O(n^ω + 2^O(g)n² log n) time using annotations.

The coverage area of a directional antenna located at point p is a circular sector of angle α, whose orientation and radius can be adjusted. The interference at p, denoted I(p), is the number of antennas that cover p, and the interference of a communication graph G = (P, E) is I(G) = max { I(p) : p ∈ P }. In this paper we address the question in its title. That is, we study several variants of the following problem: What is the minimum interference I, such that for any set P of n points in the plane, representing transceivers equipped with a directional antenna of angle α, one can assign orientations and ranges to the points in P, so that the induced communication graph G is either connected or strongly connected and I(G) ≤ I.

In the asymmetric model (i.e., G is required to be strongly connected), we prove that I = O(1) for α < 2π/3, in contrast with I = Θ(log n) for α = 2π, proved by Korman [K11]. In the symmetric model (i.e., G is required to be connected), the situation is less clear. We show that I = Θ(n) for α < π/2, and prove that I = O(n^1/2) for π/2 ≤ α ≤ 3π/2, by applying the Erdős-Szekeres theorem. The corresponding result for α = 2π is I = Θ(n^1/2), proved by Halldórsson and Tokuyama [HT08].

As in [K11] and [HT08] who deal with the case α = 2π, in both models, we assign ranges that are bounded by some constant c, assuming that UDG(P) (i.e., the unit disk graph over P) is connected. Moreover, the O(n^1/2) bound in the symmetric model reduces to O(∆^1/2), where ∆ is the maximum degree in UDG(P).

Let S be a set of n points in d-space. A convex Steiner partition is a tiling of conv(S) with empty convex bodies. For every integer d, we show that S admits a convex Steiner partition with at most ⌈(n − 1)/d⌉ tiles. This bound is the best possible for affine independent points in the plane, and it is best possible apart from constant factors in every dimension d ≥ 3. We also give the first constant-factor approximation algorithm for computing a minimum Steiner convex partition of an affine independent point set in the plane. Determining the maximum possible volume of a single tile in a Steiner partition is equivalent to a famous problem of Danzer and Rogers. We give a (1 − ε)-approximation for the maximum volume of an empty convex body when S lies in the d-dimensional unit box [0,1]^d.

Christofides' algorithm is a well known approximation algorithm for the metric travelling salesman problem. As a first step towards obtaining an average case analysis of Christofides' algorithm, we provide a probabilistic analysis for the stochastic version of the algorithm for the Euclidean traveling salesman problem, where the input consists of n randomly chosen points in the d-dimensional unit hypercube. Our main result provides bounds for the length of the computed tour that hold almost surely. We also provide an experimental evaluation of Christofides's algorithm.

In this paper, we consider the Unsplittable (hard) Capacitated Facility Location Problem (UCFLP) with uniform capacities and present some new approximation algorithms for it. This problem is a generalization of the classical facility location problem where each facility can serve at most u units of demand and each client must be served by exactly one facility. It is known that it is NP-hard to approximate this problem within any factor without violating the capacities. So we consider bicriteria (α, β)-approximations where the algorithm returns a solution whose cost is within factor α of the optimum and violates the capacity constraints within factor β. We present a framework for designing bicriteria approximation algorithms and show two new approximation algorithms with factors (10.173, 3/2) and (30.432, 4/3). These are the first algorithms with constant approximation in which the violation of capacities is below 2. The heart of our algorithms is a reduction from the UCFLP to a restricted version of the problem. One feature of this reduction is that any (O(1), 1+ε)-approximation for the restricted version implies an (O(1), 1+ε)-approximation for the UCFLP for any constant ε > 0 and we believe our techniques might be useful towards finding such approximations or perhaps (f(ε), 1+ε)-approximation for the UCFLP for some function f. In addition, we present a quasi-polynomial time (1+ε, 1+ε)-approximation for the (uniform) UCFLP in Euclidean metrics, for any constant ε > 0.

We consider the following variant of the speed scaling problem introduced by Yao, Demers, and Shenker. We are given a set of jobs and we have a variable-speed processor to process them. The higher the processor speed, the higher the energy consumption. Each job is associated with its own release time, deadline, and processing volume. The objective is to find a feasible schedule that minimizes the energy consumption. Moreover, no preemption of jobs is allowed.

It is somehow surprising that the non-premptive version of the speed scaling problem has never been studied since Yao et al. introduced the problem back in 1995. Unlike the preemptive version that is known to be in P, the non-preemptive version is strongly NP-hard. In this work, we present a constant factor approximation algorithm for it. The main technical idea is to transform the problem into the unreleated machine scheduning problem with L_p-norm objective.

The NP-complete PERMUTATION PATTERN MATCHING problem asks whether a permutation P can be matched into a permutation T. A matching is an order-preserving embedding of P into T. We present a fixed-parameter algorithm solving this problem with an exponential worst-case runtime of O*(1.79^run(T)), where run(T) denotes the number of alternating runs of T. This is the first algorithm that improves upon the O*(2ⁿ) runtime required by brute-force search without imposing restrictions on P and T. Furthermore we prove that – under standard complexity theoretic assumptions – such a fixed-parameter tractability result is not possible for run(P).

In this paper we consider a variant of the orthogonal range reporting problem when all points should be reported in the sorted order of their x-coordinates. We show that reporting two-dimensional points with this additional condition can be organized (almost) as efficiently as the standard range reporting.

Moreover, our results generalize and improve the previously known results for the orthogonal range successor problem and can be used to obtain better solutions for some stringology problems.

We consider the problem of indexing a string t of length n to report the occurrences of a query pattern p containing m characters and j wildcards. Let occ be the number of occurrences of p in t, and σ the size of the alphabet. We obtain the following results.

• A linear space index with query time O(m + σ ^j log log n + occ). This significantly improves the previously best known linear space index by Lam et al. [ISAAC 2007], which requires query time Θ(jn) in the worst case.
• An index with query time O(m + j + occ) using space O(σ^k2 n log^k log n), where k is the maximum number of wildcards allowed in the pattern. This is the first non-trivial bound with this query time.
• A time-space trade-off, generalizing the index described by Cole et al. [STOC 2004].

Our results are obtained using a novel combination of well-known and new techniques, which could be of independent interest.

We consider range queries in arrays that search for low-frequency elements: least frequent elements and α-minorities. An α-minority of a query range has multiplicity no greater than an α fraction of the elements in the range. Our data structure for the least frequent element range query problem requires O(n) space, O(n^3/2) preprocessing time, and O(n^1/2) query time. A reduction from boolean matrix multiplication to this problem shows the hardness of simultaneous improvements in both preprocessing time and query time. Our data structure for the α-minority range query problem requires O(n) space and O(1/α) query time, and allows α to be specified at query time. We apply a similar technique to solve the α-majority range query problem in O(n log n) space and O(1/α) query time. Previous work on the α-majority range query problem considers only the case when α is fixed during the construction of the data structure (Durocher et al., ICALP 2011).

We show that the asynchronous push-pull protocol spreads rumors in preferential attachment graphs in time O(log^1/2 n) to all but a lower order fraction of the nodes with high probability. This is significantly faster than what synchronized protocols can achieve; an obvious lower bound for these is the average distance, which is known to be Θ(log n / log log n) for preferential attachment graphs.

We consider dynamic subgraph connectivity problems for planar graphs. In this model there is a fixed underlying planar graph, where each edge and vertex is either "off" (failed) or "on" (recovered). We wish to answer connectivity queries with respect to the "on" subgraph.

The model has two natural variants, one in which there are d edge/vertex failures that precede all connectivity queries, and one in which failures/recoveries and queries are intermixed.

We present a d-failure connectivity oracle for planar graphs that processes any d edge/vertex failures in sort(d, n) time so that connectivity queries can be answered in pred(d, n) time. (Here sort and pred are the time for integer sorting and integer predecessor search over a subset of [n] of size d.) Our algorithm has two discrete parts. The first is an algorithm tailored to triconnected planar graphs. It makes use of Barnette's theorem, which states that every triconnected planar graph contains a degree-3 spanning tree.

The second part is a generic reduction from general (planar) graphs to triconnected (planar) graphs. We extend this algorithm to the subgraph connectivity model where edge/vertex failures (but no recoveries) are intermixed with connectivity queries. In triconnected planar graphs each failure and query is handled in O(log n) time (amortized), whereas in general planar graphs both bounds become O(log² n).

Access graphs, which have been used previously in connection with competitive analysis to model locality of reference in paging, are considered in connection with relative worst order analysis. In this model, FWF is shown to be strictly worse than both LRU and FIFO on any access graph. LRU is shown to be strictly better than FIFO on paths and cycles, but they are incomparable on some families of graphs which grow with the length of the sequences.

We study the well-known frequent items problem in data streams from a competitive analysis point of view.

We consider the standard worst-case input model, as well as a weaker distributional adversarial setting. We are primarily interested in the single-slot memory case and for both models we give (asymptotically) tight bounds of Θ(N^1/2) and Θ(N^1/3) respectively, achieved by very simple and natural algorithms, where N is the stream's length. We also provide lower bounds, for both models, in the more general case of arbitrary memory sizes of k ≥ 1.

Assuming the AND-distillation conjecture, the Pathwidth problem of determining whether a given graph G has pathwidth at most k admits no polynomial kernelization with respect to k. The present work studies the existence of polynomial kernels for Pathwidth with respect to other, structural, parameters.

Our main result is that, unless NP ⊆ coNP/poly, Pathwidth admits no polynomial kernelization even when parameterized by the vertex deletion distance to a clique, by giving a cross-composition from Cutwidth. The cross-composition works also for Treewidth, improving over previous lower bounds by the present authors. For Pathwidth, our result rules out polynomial kernels with respect to the distance to various classes of polynomial-time solvable inputs, like interval or cluster graphs.

This leads to the question whether there are nontrivial structural parameters for which Pathwidth does admit a polynomial kernelization. To answer this, we give a collection of graph reduction rules that are safe for Pathwidth. We analyze the success of these results and obtain polynomial kernelizations with respect to the following parameters: the size of a vertex cover of the graph, the vertex deletion distance to a graph where each connected component is a star, and the vertex deletion distance to a graph where each connected component has at most c vertices.

This work further explores the applications of co-nondeterminism for showing kernelization lower bounds. The only known example excludes polynomial kernelizations for the RAMSEY problem of finding an independent set or a clique of at least k vertices in a given graph (Kratsch 2012, SODA). We study the more general problem of finding induced subgraphs on k vertices fulfilling some hereditary property Π, called Π-INDUCED SUBGRAPH. The problem is NP-hard for all non-trivial choices of Π by a classic result of Lewis and Yannakakis (JCSS 1980). The parameterized complexity of this problem was classified by Khot and Raman (TCS 2002) depending on the choice of Π. The interesting cases for kernelization are for Π containing all independent sets and all cliques, since the problem is trivial or W[1]-hard otherwise.

Our results are twofold. Regarding Π-INDUCED SUBGRAPH, we show that for a large choice of natural graph properties Π, including chordal, perfect, cluster, and cograph, there is no polynomial kernel with respect to k. This is established by two proofs: one using a co-nondeterministic variant of cross-composition and one by a polynomial parameter transformation from RAMSEY. The latter result is inspired by a second coNP-composition-based proof which is included in the full version.

Additionally, we show how to use improvement versions of NP-hard problems as source problems for lower bounds, without requiring their NP-hardness. E.g., for Π-INDUCED SUBGRAPH our compositions may assume existing solutions of size k − 1. We believe this to be useful for further lower bound proofs, since improvement versions simplify the construction of a disjunction (OR) of instances required in compositions. This adds a second way of using co-nondeterminism for lower bounds.

We study the query complexity of testing for properties defined by read once formulae, as instances of massively parametrized properties, and prove several testability and non-testability results. First we prove the testability of any property accepted by a Boolean read-once formula involving any bounded arity gates with a number of queries exponential in ε and independent of all other parameters. When the gates are limited to being monotone, we prove that there is an estimation algorithm, that outputs an approximation of the distance of the input from satisfying the property. For formulae only involving And/Or gates, we provide a more efficient test whose query complexity is only quasipolynomial in ε. On the other hand we show that such testability results do not hold in general for formulae over non-Boolean alphabets; specifically we construct a property defined by a read-once arity 2 (non-Boolean) formula over alphabets of size 4, such that any 1/4-test for it requires a number of queries depending on the formula size.

This paper investigates the number of quantum queries made to solve the problem of reconstructing an unknown string from its substrings in a certain query model. More concretely, the goal of the problem is to identify an unknown string S by making queries of the following form: "Is s a substring of S?", where s is a query string over the given alphabet. The number of queries required to identify the string S is the query complexity of this problem.

First we show a quantum algorithm that exactly identifies the string S with at most ¾N + o(N) queries, where N is the length of S. This contrasts sharply with the classical query complexity N. Our algorithm uses Skiena and Sundaram's classical algorithm and the Grover search as subroutines. To make them effectively work, we develop another subroutine that finds a string appearing only once in S, which may have an independent interest. We also prove two lower bounds. The first one is a general lower bound of Ω(N/log² N), which means we cannot achieve a query complexity of O(N^1−ε) for any constant ε. The other one claims that if we cannot use queries of length roughly between log N and 3 log N, then we cannot achieve a query complexity of any sublinear function in N.