Arrow Research search

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.

9 papers
2 author rows

Possible papers

9

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

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