Parameterized Testability
Kazuo Iwama, Yuichi Yoshida
Article No.: 16
DOI: 10.1145/3155294

This article studies property testing for NP optimization problems with parameter k under the general graph model with an augmentation of random edge sampling capability. It is shown that a variety of such problems, including...

Parameterized Property Testing of Functions
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
Article No.: 17
DOI: 10.1145/3155296

We investigate the parameters in terms of which the complexity of sublinear-time algorithms should be expressed. Our goal is to find input parameters that are tailored to the combinatorics of the specific problem being studied and design...

On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs
Michał Pilipczuk, Marcin Wrochna
Article No.: 18
DOI: 10.1145/3154856

Dynamic programming on path and tree decompositions of graphs is a technique that is ubiquitous in the field of parameterized and exponential-time algorithms. However, one of its drawbacks is that the space usage is exponential in the...

An O(n^ε) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
Diptarka Chakraborty, Raghunath Tewari
Article No.: 19
DOI: 10.1145/3154857

Given a graph G and two vertices s and t in it, graph reachability is the problem of checking whether there exists a path from s to t in G. We show that reachability in directed layered planar...

Metric 1-Median Selection: Query Complexity vs. Approximation Ratio
Ching-Lueh Chang
Article No.: 20
DOI: 10.1145/3154858

Consider the problem of finding a point in a metric space ({ 1,2,&ldots;, n}, d) with the minimum average distance to other points. We show that this problem has no deterministic...