Author name cluster

Michael Elberfeld

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

2 author rows

CSL Conference 2016 Conference Paper

Context-Free Graph Properties via Definable Decompositions

Michael Elberfeld

Monadic-second order logic (MSO-logic) is successfully applied in both language theory and algorithm design. In the former, properties definable by MSO-formulas are exactly the regular properties on many structures like, most prominently, strings. In the latter, solving a problem for structures of bounded tree width is routinely done by defining it in terms of an MSO-formula and applying general formula-evaluation procedures like Courcelle's. The present paper furthers the study of second-order logics with close connections to language theory and algorithm design beyond MSO-logic. We introduce a logic that allows to expand a given structure with an existentially quantified tree decomposition of bounded width and test an MSO-definable property for the resulting expanded structure. It is proposed as a candidate for capturing the notion of "context-free graph properties" since it corresponds to the context-free languages on strings, has the same closure properties, and an alternative definition similar to the one of Chomsky and Schützenberger for context-free languages. Besides studying its language-theoretic aspects, we consider its expressive power as well as the algorithmics of its satisfiability and evaluation problems.

Details

Highlights Conference 2016 Conference Abstract

Order Invariance on Decomposable Structures

Michael Elberfeld
Marlin Frickenschmidt
Martin Grohe

Order-invariant formulas access an ordering on a structure’s universe, but the model relation is independent of the used ordering. Order invariance is frequently used for logic-based approaches in computer science. Order-invariant formulas capture unordered problems of complexity classes and they model the independence of the answer to a database query from low-level aspects of databases. We study the expressive power of order-invariant monadic second-order (MSO) and first-order (FO) logic on restricted classes of structures that admit certain forms of tree decompositions (not necessarily of bounded width). While order-invariant MSO is more expressive than MSO and, even, CMSO (MSO with modulo-counting predicates), we show that order-invariant MSO and CMSO are equally expressive on graphs of bounded tree width and on planar graphs. This extends an earlier result for trees due to Courcelle. Moreover, we show that all properties definable in order-invariant FO are also definable in MSO on these classes. These results are applications of a theorem that shows how to lift up definability results for order-invariant logics from the bags of a graph’s tree decomposition to the graph itself. This is joint work with Michael Elberfeld and Martin Grohe. It was accepted to LICS 2016.

Details

STOC Conference 2014 Conference Paper

Embedding and canonizing graphs of bounded genus in logspace

Michael Elberfeld
Ken-ichi Kawarabayashi

Graph embeddings of bounded Euler genus (that means, embeddings with bounded orientable or nonorientable genus) help to design time-efficient algorithms for many graph problems. Since linear-time algorithms are known to compute embeddings of any bounded Euler genus, one can always assume to work with embedded graphs and, thus, obtain fast algorithms for many problems on any class of graphs of bounded Euler genus. Problems on graphs of bounded Euler genus are also important from the perspective of finding space-efficient algorithms, mostly focusing on problems related to finding paths and matchings in graphs. So far, known space-bounded approaches needed the severe assumption that an embedding is given as part of the input since no space-efficient embedding procedure for nonplanar graphs was known. The present work sidesteps this assumption and shows that embeddings of any bounded Euler genus can be computed in deterministic logarithmic space (logspace); allowing to generalize results on the space complexity of path and matching problems from embedded graphs to graphs of bounded Euler genus. The techniques developed for the embedding procedure also allow to compute canonical representations and, thus, solve the isomorphism problem for graphs of bounded Euler genus in logspace.

Details

Highlights Conference 2014 Conference Abstract

Invited talk: Monadic Second-Order Definable Problems in Computational Complexity Theory

Michael Elberfeld

Applying problem definitions in terms of monadic-second order (MSO) formulas in conjunction with evaluation procedures for tree-width-bounded graphs and reductions to them is a common approach to design efficient algorithms. Beside simplifying known proofs, this algorithmic paradigm has proven to help develop new efficient algorithms. Just like many problems in algorithmics are MSO-definable, the same is true for a large number of problems studied in the realm of parallel and space complexity classes inside deterministic polynomial time. Thus, understanding the fine-grained complexity-theoretic aspects of evaluating formulas in MSO-logic as well as its restrictions and generalizations has a great potential. The talk first surveys recent developments on approaches for evaluating MSO-formulas on tree-width-bounded graphs in terms of uniform circuits and logarithmic space. Then current and possible future complexity-theoretic applications for MSO-definitions and tree width reductions are discussed. 10: 00 10: 30 Breakfast & coffee

PDF Details

TCS Journal 2013 Journal Article

Approximation algorithms for orienting mixed graphs

Michael Elberfeld
Danny Segev
Colin R. Davidson
Dana Silverbush
Roded Sharan

Graph orientation is a fundamental problem in graph theory that has recently arisen in the study of signaling-regulatory pathways in protein networks. Given a graph and a list of source–target vertex pairs, one wishes to assign directions to the edges so as to maximize the number of pairs that admit a directed source-to-target path. When the input graph is undirected, a sub-logarithmic approximation is known for this problem. However, the approximability of the biologically-relevant variant, in which the input graph has both directed and undirected edges, was left open. Here we give the first approximation algorithms to this problem. Our algorithms provide a sub-linear guarantee in the general case, and logarithmic guarantees for structured instances.

Details DOI

TCS Journal 2012 Journal Article

Influence of tree topology restrictions on the complexity of haplotyping with missing data

Michael Elberfeld
Ilka Schnoor
Till Tantau

Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast haplotyping method is based on an evolutionary model in which a perfect phylogenetic tree is sought that explains the observed data. Unfortunately, when data entries are missing, which is often the case in laboratory data, the resulting formal problem ipph, which stands for incomplete perfect phylogeny haplotyping, is NP -complete. Even radically simplified versions, such as the restriction to phylogenetic trees consisting of just two directed paths from a given root, are still NP -complete; but here, at least, a fixed-parameter algorithm is known. Such drastic and ad hoc simplifications turn out to be unnecessary to make ipph tractable: we present the first theoretical analysis of a parameterized algorithm, which we develop in the course of the paper, that works for arbitrary instances of ipph. This tractability result is optimal insofar as we prove ipph to be NP -complete whenever any of the parameters we consider is not fixed, but part of the input.

Details DOI

I&C Journal 2012 Journal Article

Phylogeny- and parsimony-based haplotype inference with constraints

Michael Elberfeld
Till Tantau

Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast computational haplotyping method is based on an evolutionary model where a perfect phylogenetic tree is sought that explains the observed data. An extension of this approach tries to incorporate prior knowledge in the form of a set of candidate haplotypes from which the right haplotypes must be chosen. The objective is to increase the accuracy of haplotyping methods, but it was conjectured that the resulting formal problem constrained perfect phylogeny haplotyping might be NP-complete. In the paper at hand we present a polynomial-time algorithm for it. Our algorithmic ideas also yield new fixed-parameter algorithms for related haplotyping problems based on the maximum parsimony assumption.

Details DOI

TCS Journal 2011 Journal Article

Negative selection algorithms on strings with efficient training and linear-time classification

Michael Elberfeld
Johannes Textor

A string-based negative selection algorithm is an immune-inspired classifier that infers a partitioning of a string space Σ ℓ into “normal” and “anomalous” partitions from a training set S containing only samples from the “normal” partition. The algorithm generates a set of patterns, called “detectors”, to cover regions of the string space containing none of the training samples. Strings that match at least one of these detectors are then classified as “anomalous”. A major problem with existing implementations of this approach is that the detector generating step needs exponential time in the worst case. Here we show that for the two most widely used kinds of detectors, the r -chunk and r -contiguous detectors based on partial matching to substrings of length r, negative selection can be implemented more efficiently by avoiding generating detectors altogether: for each detector type, training set S ⊆ Σ ℓ and parameter r ≤ ℓ one can construct an automaton whose acceptance behaviour is equivalent to the algorithm’s classification outcome. The resulting runtime is O ( | S | ℓ r | Σ | ) for constructing the automaton in the training phase and O ( ℓ ) for classifying a string.

Details DOI

FOCS Conference 2010 Conference Paper

Logspace Versions of the Theorems of Bodlaender and Courcelle

Michael Elberfeld
Andreas Jakoby
Till Tantau

Bodlaender's Theorem states that for every k there is a linear-time algorithm that decides whether an input graph has tree width k and, if so, computes a width-k tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula φ and for every k there is a linear-time algorithm that decides whether a given logical structure A of tree width at most k satisfies φ. We prove that both theorems still hold when "linear time" is replaced by "logarithmic space. " The transfer of the powerful theoretical framework of monadic second-order logic and bounded tree width to logarithmic space allows us to settle a number of both old and recent open problems in the log space world.

Details

MFCS Conference 2008 Conference Paper

Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems

Michael Elberfeld
Till Tantau

Abstract Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. This problem, which has strong practical applications, can be approached using both statistical as well as combinatorial methods. While the most direct combinatorial approach, maximum parsimony, leads to NP-complete problems, the perfect phylogeny model proposed by Gusfield yields a problem, called pph, that can be solved in polynomial (even linear) time. Even this may not be fast enough when the whole genome is studied, leading to the question of whether parallel algorithms can be used to solve the pph problem. In the present paper we answer this question affirmatively, but we also give lower complexity bounds on its complexity. In detail, we show that the problem lies in Mod 2 L, a subclass of the circuit complexity class NC 2, and is hard for logarithmic space and thus presumably not in NC 1. We also investigate variants of the pph problem that have been studied in the literature, like the perfect path phylogeny haplotyping problem and the combined problem where a perfect phylogeny of maximal parsimony is sought, and show that some of these variants are TC 0 -complete or lie in AC 0.

Details