Source author record

Isolde Adler

Isolde Adler appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms math.CO Discrete Mathematics Logic in Computer Science Databases math.LO Computational Complexity

Catalog footprint

What is connected

10works

7topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2021arXiv

On Testability of First-Order Properties in Bounded-Degree Graphs

We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that is defined by a formula with quantifier prefix $\exists^*\forall^*$ is testable (i.e., testable with constant query complexity), while there exists an FO property that is expressible by a formula with quantifier prefix $\forall^*\exists^*$ that is not testable. In the dense graph model, a similar picture is long known (Alon, Fischer, Krivelevich, Szegedy, Combinatorica 2000), despite the very different nature of the two models. In particular, we obtain our lower bound by a first-order formula that defines a class of bounded-degree expanders, based on zig-zag products of graphs. We expect this to be of independent interest. We then prove testability of some first-order properties that speak about isomorphism types of neighbourhoods, including testability of $1$-neighbourhood-freeness, and $r$-neighbourhood-freeness under a mild assumption on the degrees.

preprint2021arXiv

Towards Approximate Query Enumeration with Sublinear Preprocessing Time

This paper aims at providing extremely efficient algorithms for approximate query enumeration on sparse databases, that come with performance and accuracy guarantees. We introduce a new model for approximate query enumeration on classes of relational databases of bounded degree. We first prove that on databases of bounded degree any local first-order definable query can be enumerated approximately with constant delay after a constant time preprocessing phase. We extend this, showing that on databases of bounded tree-width and bounded degree, every query that is expressible in first-order logic can be enumerated approximately with constant delay after a sublinear (more precisely, polylogarithmic) time preprocessing phase. Durand and Grandjean (ACM Transactions on Computational Logic 2007) proved that exact enumeration of first-order queries on databases of bounded degree can be done with constant delay after a linear time preprocessing phase. Hence we achieve a significant speed-up in the preprocessing phase. Since sublinear running time does not allow reading the whole input database even once, sacrificing some accuracy is inevitable for our speed-up. Nevertheless, our enumeration algorithms come with guarantees: With high probability, (1) only tuples are enumerated that are answers to the query or `close' to being answers to the query, and (2) if the proportion of tuples that are answers to the query is sufficiently large, then all answers will be enumerated. Here the notion of `closeness' is a tuple edit distance in the input database. For local first-order queries, only actual answers are enumerated, strengthening (1). Moreover, both the `closeness' and the proportion required in (2) are controllable. We combine methods from property testing of bounded degree graphs with logic and query enumeration, which we believe can inspire further research.

preprint2020arXiv

Faster Property Testers in a Variation of the Bounded Degree Model

Property testing algorithms are highly efficient algorithms, that come with probabilistic accuracy guarantees. For a property P, the goal is to distinguish inputs that have P from those that are far from having P with high probability correctly, by querying only a small number of local parts of the input. In property testing on graphs, the distance is measured by the number of edge modifications (additions or deletions), that are necessary to transform a graph into one with property P. Much research has focussed on the query complexity of such algorithms, i. e. the number of queries the algorithm makes to the input, but in view of applications, the running time of the algorithm is equally relevant. In (Adler, Harwath STACS 2018), a natural extension of the bounded degree graph model of property testing to relational databases of bounded degree was introduced, and it was shown that on databases of bounded degree and bounded tree-width, every property that is expressible in monadic second-order logic with counting (CMSO) is testable with constant query complexity and sublinear running time. It remains open whether this can be improved to constant running time. In this paper we introduce a new model, which is based on the bounded degree model, but the distance measure allows both edge (tuple) modifications and vertex (element) modifications. Our main theorem shows that on databases of bounded degree and bounded tree-width, every property that is expressible in CMSO is testable with constant query complexity and constant running time in the new model. We also show that every property that is testable in the classical model is testable in our model with the same query complexity and running time, but the converse is not true. We argue that our model is natural and our meta-theorem showing constant-time CMSO testability supports this.

preprint2020arXiv

Vapnik-Chervonenkis Dimension and Density on Johnson and Hamming Graphs

VC-dimension and VC-density are measures of combinatorial complexity of set systems. VC-dimension was first introduced in the context of statistical learning theory, and is tightly related to the sample complexity in PAC learning. VC-density is a refinement of VC-dimension. Both notions are also studied in model theory, in the context of \emph{dependent} theories. A set system that is definable by a formula of first-order logic with parameters has finite VC-dimension if and only if the formula is a dependent formula. In this paper we study the VC-dimension and the VC-density of the edge relation $Exy$ on Johnson graphs and on Hamming graphs. On a graph $G$, the set system defined by the formula $Exy$ is the vertex set of $G$ along with the collection of all \emph{open neighbourhoods} of $G$. We show that the edge relation has VC-dimension at most $4$ on Johnson graphs and at most $3$ on Hamming graphs and these bounds are optimal. We furthermore show that the VC-density of the edge relation on the class of all Johnson graphs is $2$, and on the class of all Hamming graphs the VC-density is $2$ as well. Moreover, we show that our bounds on the VC-dimension carry over to the class of all induced subgraphs of Johnson graphs, and to the class of all induced subgraphs of Hamming graphs, respectively. It also follows that the VC-dimension of the set systems of \emph{closed neighbourhoods} in Johnson graphs and Hamming graphs is bounded. Johnson graphs and Hamming graphs are well known examples of distance transitive graphs. Neither of these graph classes is nowhere dense nor is there a bound on their (local) clique-width. Our results contrast this by giving evidence of structural tameness of the graph classes.

preprint2016arXiv

Irrelevant Vertices for the Planar Disjoint Paths Problem

The Disjoint Paths Problem asks, given a graph $G$ and a set of pairs of terminals $(s_{1},t_{1}),\ldots,(s_{k},t_{k})$, whether there is a collection of $k$ pairwise vertex-disjoint paths linking $s_{i}$ and $t_{i}$, for $i=1,\ldots,k.$ In their $f(k)\cdot n^{3}$ algorithm for this problem, Robertson and Seymour introduced the irrelevant vertex technique according to which in every instance of treewidth greater than $g(k)$ there is an "irrelevant" vertex whose removal creates an equivalent instance of the problem. This fact is based on the celebrated Unique Linkage Theorem, whose - very technical - proof gives a function $g(k)$ that is responsible for an immense parameter dependence in the running time of the algorithm. In this paper we give a new and self-contained proof of this result that strongly exploits the combinatorial properties of planar graphs and achieves $g(k)=O(k^{3/2}\cdot 2^{k}).$ Our bound is radically better than the bounds known for general graphs.

preprint2015arXiv

Linear rank-width of distance-hereditary graphs I. A polynomial-time algorithm

Linear rank-width is a linearized variation of rank-width, and it is deeply related to matroid path-width. In this paper, we show that the linear rank-width of every $n$-vertex distance-hereditary graph, equivalently a graph of rank-width at most $1$, can be computed in time $\mathcal{O}(n^2\cdot \log_2 n)$, and a linear layout witnessing the linear rank-width can be computed with the same time complexity. As a corollary, we show that the path-width of every $n$-element matroid of branch-width at most $2$ can be computed in time $\mathcal{O}(n^2\cdot \log_2 n)$, provided that the matroid is given by an independent set oracle. To establish this result, we present a characterization of the linear rank-width of distance-hereditary graphs in terms of their canonical split decompositions. This characterization is similar to the known characterization of the path-width of forests given by Ellis, Sudborough, and Turner [The vertex separation and search number of a graph. Inf. Comput., 113(1):50--79, 1994]. However, different from forests, it is non-trivial to relate substructures of the canonical split decomposition of a graph with some substructures of the given graph. We introduce a notion of `limbs' of canonical split decompositions, which correspond to certain vertex-minors of the original graph, for the right characterization.

preprint2015arXiv

Planar Disjoint-Paths Completion

introduce {\sc Planar Disjoint Paths Completion}, a completion counterpart of the Disjoint Paths problem, and study its parameterized complexity. The problem can be stated as follows: given a, not necessarily connected, plane graph $G,$ $k$ pairs of terminals, and a face $F$ of $G,$ find a minimum-size set of edges, if one exists, to be added inside $F$ so that the embedding remains planar and the pairs become connected by $k$ disjoint paths in the augmented network. Our results are twofold: first, we give an upper bound on the number of necessary additional edges when a solution exists. This bound is a function of $k$, independent of the size of $G.$ Second, we show that the problem is fixed-parameter tractable, in particular, it can be solved in time $f(k)\cdot n^{2}.$

preprint2011arXiv

Obstructions for linear rankwidth at most 1

We provide a characterization of graphs of linear rankwidth at most 1 by minimal excluded vertex-minors.

preprint2010arXiv

A lower bound for the tree-width of planar graphs with vital linkages

The disjoint paths problem asks, given an graph G and k + 1 pairs of terminals (s_0,t_0), ...,(s_k,t_k), whether there are k+1 pairwise disjoint paths P_0, ...,P_k, such that P_i connects s_i to t_i. Robertson and Seymour have proven that the problem can be solved in polynomial time if k is fixed. Nevertheless, the constants involved are huge, and the algorithm is far from implementable. The algorithm uses a bound on the tree-width of graphs with vital linkages, and deletion of irrelevant vertices. We give single exponential lower bounds both for the tree-width of planar graphs with vital linkages, and for the size of the grid necessary for finding irrelevant vertices.