Author name cluster

Kord Eickmeyer

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.

4 papers

2 author rows

TCS Journal 2018 Journal Article

Gap-planar graphs

Sang Won Bae
Jean-Francois Baffier
Jinhee Chun
Peter Eades
Kord Eickmeyer
Luca Grilli
Seok-Hee Hong
Matias Korman

We introduce the family of k-gap-planar graphs for k ≥ 0, i. e. , graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings. This definition is motivated by applications in edge casing, as a k-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We present results on the maximum density of k-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of k-gap-planar complete graphs, and the computational complexity of recognizing k-gap-planar graphs.

Details DOI

CSL Conference 2016 Conference Paper

Successor-Invariant First-Order Logic on Graphs with Excluded Topological Subgraphs

Kord Eickmeyer
Ken-ichi Kawarabayashi

We show that the model-checking problem for successor-invariant first-order logic is fixed-parameter tractable on graphs with excluded topological subgraphs when parameterised by both the size of the input formula and the size of the exluded topological subgraph. Furthermore, we show that model-checking for order-invariant first-order logic is tractable on coloured posets of bounded width, parameterised by both the size of the input formula and the width of the poset. Results of this form, i. e. showing that model-checking for a certain logic is tractable on a certain class of structures, are often referred to as algorithmic meta-theorems since they give a unified proof for the tractability of a whole range of problems. First-order logic is arguably one of the most important logics in this context since it is powerful enough to express many computational problems (e. g. the existence of cliques, dominating sets etc.) and yet its model-checking problem is tractable on rich classes of graphs. In fact, Grohe et al have shown that model-checking for FO is tractable on all nowhere dense classes of graphs. Successor-invariant FO is a semantic extension of FO by allowing the use of an additional binary relation which is interpreted as a directed Hamiltonian cycle, restricted to formulae whose truth value does not depend on the specific choice of a Hamiltonian cycle. While this is very natural in the context of model-checking (after all, storing a structure in computer memory usually brings with it a linear order on the structure), the question of how the computational complexity of the model-checking problem for this richer logic compares to that of plain FO is still open. Our result for successor-invariant FO extends previous results for this logic on planar graphs and graphs with excluded minors, further narrowing the gap between what is known for FO and what is known for successor-invariant FO. The proof uses Grohe and Marx's structure theorem for graphs with excluded topological subgraphs. For order-invariant FO we show that Gajarský et al. 's recent result for FO carries over to order-invariant FO.

Details

CSL Conference 2011 Conference Paper

Non-Definability Results for Randomised First-Order Logic

Kord Eickmeyer

We investigate the expressive power of randomised first-order logic (BPFO) on restricted classes of structures. While BPFO is stronger than FO in general, even on structures with a built-in addition relation, we show that BPFO is not stronger than FO on structures with a unary vocabulary, nor on the class of equivalence relations. The same techniques can be applied to show that evenness of a linear order, and therefore graph connectivity, can not be defined in BPFO. Finally, we show that there is an FO[<]-definable query on word structures which can not be defined in BPFO[+1].

Details

CSL Conference 2010 Conference Paper

Randomisation and Derandomisation in Descriptive Complexity Theory

Kord Eickmeyer
Martin Grohe

Abstract We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic L we introduce a new logic BPL, bounded error probabilistic L, which is defined from L in a similar way as the complexity class BPP, bounded error probabilistic polynomial time, is defined from P. Our main focus lies on questions of derandomisation, and we prove that there is a query which is definable in BPFO, the probabilistic version of first-order logic, but not in C \(^\omega_{\infty{\omega}}\), finite variable infinitary logic with counting. This implies that many of the standard logics of finite model theory, like transitive closure logic and fixed-point logic, both with and without counting, cannot be derandomised. We prove similar results for ordered structures and structures with an addition relation, showing that certain uniform variants of A C 0 (bounded-depth polynomial sized circuits) cannot be derandomised. These results are in contrast to the general belief that most standard complexity classes can be derandomised. Finally, we note that BPIFP+C, the probabilistic version of fixed-point logic with counting, captures the complexity class BPP, even on unordered structures.

Details