7 Search Results for "Eickmeyer, Kord"

Document
DOI: 10.4230/LIPIcs.ESA.2025.21
A Unified FPT Framework for Crossing Number Problems

Authors: Éric Colin de Verdière and Petr Hliněný

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The basic (and traditional) crossing number problem is to determine the minimum number of crossings in a topological drawing of an input graph in the plane. We develop a unified framework that smoothly captures many generalized crossing number problems, and that yields fixed-parameter tractable (FPT) algorithms for them not only in the plane but also on surfaces. Our framework takes the following form. We fix a surface S, an integer r, and a map κ from the set of topological drawings of graphs in S to ℤ_+ ∪ {∞}, satisfying some natural monotonicity conditions, but essentially describing the allowed drawings and how we want to count the crossings in them. Then deciding whether an input graph G has an allowed drawing D on S with κ(D) ≤ r can be done in time quadratic in the size of G (and exponential in other parameters). More generally, we may take as input an edge-colored graph, and distinguish crossings by the colors of the involved edges; and we may allow to perform a bounded number of edge removals and vertex splits to G before drawing it. The proof is a reduction to the embeddability of a graph on a two-dimensional simplicial complex. This framework implies, in a unified way, quadratic FPT algorithms for many topological crossing number variants established in the graph drawing community. Some of these variants already had previously published FPT algorithms, mostly relying on Courcelle’s metatheorem, but for many of those, we obtain an algorithm with a better runtime. Moreover, our framework extends, at no cost, to these crossing number variants in any fixed surface.
Cite as

Éric Colin de Verdière and Petr Hliněný. A Unified FPT Framework for Crossing Number Problems. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{colindeverdiere_et_al:LIPIcs.ESA.2025.21,
  author =	{Colin de Verdi\`{e}re, \'{E}ric and Hlin\v{e}n\'{y}, Petr},
  title =	{{A Unified FPT Framework for Crossing Number Problems}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.21},
  URN =		{urn:nbn:de:0030-drops-244897},
  doi =		{10.4230/LIPIcs.ESA.2025.21},
  annote =	{Keywords: computational geometry, fixed-parameter tractability, graph drawing, graph embedding, crossing number, two-dimensional simplicial complex, surface}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.14
On the Automatability of Tree-Like k-DNF Resolution

Authors: Gaia Carenini and Susanna F. de Rezende

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
A proof system 𝒫 is said to be automatable in time f(N) if there exists an algorithm that given as input an unsatisfiable formula F outputs a refutation of F in the proof system 𝒫 in time f(N), where N is the size of the smallest 𝒫-refutation of F plus the size of F. Atserias and Bonet (ECCC 2002), observed that tree-like k-DNF resolution is automatable in time N^{c⋅klog N} for a universal constant c. We show that, under the randomized exponential-time hypothesis (rETH), this is tight up to a O(log k)-factor in the exponent, i.e., we prove that tree-like k-DNF resolution, for k at most logarithmic in the number of variables of F, is not automatable in time N^o((k/log k)⋅log N) unless rETH is false. Our proof builds on the non-automatability results for resolution by Atserias and Müller (FOCS 2019), for algebraic proof systems by de Rezende, Göös, Nordström, Pitassi, Robere and Sokolov (STOC 2021), and for tree-like resolution by de Rezende (LAGOS 2021).
Cite as

Gaia Carenini and Susanna F. de Rezende. On the Automatability of Tree-Like k-DNF Resolution. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{carenini_et_al:LIPIcs.CCC.2025.14,
  author =	{Carenini, Gaia and de Rezende, Susanna F.},
  title =	{{On the Automatability of Tree-Like k-DNF Resolution}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.14},
  URN =		{urn:nbn:de:0030-drops-237081},
  doi =		{10.4230/LIPIcs.CCC.2025.14},
  annote =	{Keywords: Proof Complexity, Tree-like k-DNF Resolution, Automatability}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.21
Adjacency Labeling Schemes for Small Classes

Authors: Édouard Bonnet, Julien Duron, John Sylvester, and Viktor Zamaraev

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
A graph class admits an implicit representation if, for every positive integer n, its n-vertex graphs have a O(log n)-bit (adjacency) labeling scheme, i.e., their vertices can be labeled by binary strings of length O(log n) such that the presence of an edge between any pair of vertices can be deduced solely from their labels. The famous Implicit Graph Conjecture posited that every hereditary (i.e., closed under taking induced subgraphs) factorial (i.e., containing 2^O(n log n) n-vertex graphs) class admits an implicit representation. The conjecture was recently refuted [Hatami and Hatami, FOCS '22], and does not even hold among monotone (i.e., closed under taking subgraphs) factorial classes [Bonnet et al., ICALP '24]. However, monotone small (i.e., containing at most n! cⁿ many n-vertex graphs for some constant c) classes do admit implicit representations. This motivates the Small Implicit Graph Conjecture: Every hereditary small class admits an O(log n)-bit labeling scheme. We provide evidence supporting the Small Implicit Graph Conjecture. First, we show that every small weakly sparse (i.e., excluding some fixed bipartite complete graph as a subgraph) class has an implicit representation. This is a consequence of the following fact of independent interest proved in the paper: Every weakly sparse small class has bounded expansion (hence, in particular, bounded degeneracy). Second, we show that every hereditary small class admits an O(log³ n)-bit labeling scheme, which provides a substantial improvement of the best-known polynomial upper bound of n^(1-ε) on the size of adjacency labeling schemes for such classes. This is a consequence of another fact of independent interest proved in the paper: Every small class has neighborhood complexity O(n log n).
Cite as

Édouard Bonnet, Julien Duron, John Sylvester, and Viktor Zamaraev. Adjacency Labeling Schemes for Small Classes. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ITCS.2025.21,
  author =	{Bonnet, \'{E}douard and Duron, Julien and Sylvester, John and Zamaraev, Viktor},
  title =	{{Adjacency Labeling Schemes for Small Classes}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.21},
  URN =		{urn:nbn:de:0030-drops-226493},
  doi =		{10.4230/LIPIcs.ITCS.2025.21},
  annote =	{Keywords: Adjacency labeling, degeneracy, weakly sparse classes, small classes, implicit graph conjecture}
}
Document
DOI: 10.4230/LIPIcs.CSL.2025.15
On the VC Dimension of First-Order Logic with Counting and Weight Aggregation

Authors: Steffen van Bergerem and Nicole Schweikardt

Published in: LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Abstract
We prove optimal upper bounds on the Vapnik-Chervonenkis density of formulas in the extensions of first-order logic with counting (FOC_1) and with weight aggregation (FOWA_1) on nowhere dense classes of (vertex- and edge-)weighted finite graphs. This lifts a result of Pilipczuk, Siebertz, and Toruńczyk [Michał Pilipczuk et al., 2018] from first-order logic on ordinary finite graphs to substantially more expressive logics on weighted finite graphs. Moreover, this proves that every FOC_1 formula and every FOWA_1 formula has bounded Vapnik-Chervonenkis dimension on nowhere dense classes of weighted finite graphs; thereby, it lifts a result of Adler and Adler [Hans Adler and Isolde Adler, 2014] from first-order logic to FOC_1 and FOWA_1. Generalising another result of Pilipczuk, Siebertz, and Toruńczyk [Michał Pilipczuk et al., 2018], we also provide an explicit upper bound on the ladder index of FOC_1 and FOWA_1 formulas on nowhere dense classes. This shows that nowhere dense classes of weighted finite graphs are FOC_1-stable and FOWA_1-stable.
Cite as

Steffen van Bergerem and Nicole Schweikardt. On the VC Dimension of First-Order Logic with Counting and Weight Aggregation. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 326, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanbergerem_et_al:LIPIcs.CSL.2025.15,
  author =	{van Bergerem, Steffen and Schweikardt, Nicole},
  title =	{{On the VC Dimension of First-Order Logic with Counting and Weight Aggregation}},
  booktitle =	{33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-362-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{326},
  editor =	{Endrullis, J\"{o}rg and Schmitz, Sylvain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.15},
  URN =		{urn:nbn:de:0030-drops-227722},
  doi =		{10.4230/LIPIcs.CSL.2025.15},
  annote =	{Keywords: VC dimension, VC density, stability, nowhere dense graphs, first-order logic with weight aggregation, first-order logic with counting}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.63
Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs

Authors: Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We prove that whenever G is a graph from a nowhere dense graph class C, and A is a subset of vertices of G, then the number of subsets of A that are realized as intersections of A with r-neighborhoods of vertices of G is at most f(r,eps)|A|^(1+eps), where r is any positive integer, eps is any positive real, and f is a function that depends only on the class C. This yields a characterization of nowhere dense classes of graphs in terms of neighborhood complexity, which answers a question posed by [Reidl et al., CoRR, 2016]. As an algorithmic application of the above result, we show that for every fixed integer r, the parameterized Distance-r Dominating Set problem admits an almost linear kernel on any nowhere dense graph class. This proves a conjecture posed by [Drange et al., STACS 2016], and shows that the limit of parameterized tractability of Distance-r Dominating Set on subgraph-closed graph classes lies exactly on the boundary between nowhere denseness and somewhere denseness.
Cite as

Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{eickmeyer_et_al:LIPIcs.ICALP.2017.63,
  author =	{Eickmeyer, Kord and Giannopoulou, Archontia C. and Kreutzer, Stephan and Kwon, O-joung and Pilipczuk, Michal and Rabinovich, Roman and Siebertz, Sebastian},
  title =	{{Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{63:1--63:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.63},
  URN =		{urn:nbn:de:0030-drops-74288},
  doi =		{10.4230/LIPIcs.ICALP.2017.63},
  annote =	{Keywords: Graph Structure Theory, Nowhere Dense Graphs, Parameterized Complexity, Kernelization, Dominating Set}
}
Document
DOI: 10.4230/LIPIcs.CSL.2016.18
Successor-Invariant First-Order Logic on Graphs with Excluded Topological Subgraphs

Authors: Kord Eickmeyer and Ken-ichi Kawarabayashi

Published in: LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

Abstract
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.
Cite as

Kord Eickmeyer and Ken-ichi Kawarabayashi. Successor-Invariant First-Order Logic on Graphs with Excluded Topological Subgraphs. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{eickmeyer_et_al:LIPIcs.CSL.2016.18,
  author =	{Eickmeyer, Kord and Kawarabayashi, Ken-ichi},
  title =	{{Successor-Invariant First-Order Logic on Graphs with Excluded Topological Subgraphs}},
  booktitle =	{25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-022-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{62},
  editor =	{Talbot, Jean-Marc and Regnier, Laurent},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.18},
  URN =		{urn:nbn:de:0030-drops-65583},
  doi =		{10.4230/LIPIcs.CSL.2016.18},
  annote =	{Keywords: model-checking, algorithmic meta-theorem, successor-invariant, first-order logic, topological subgraphs, parameterised complexity}
}
Document
DOI: 10.4230/LIPIcs.CSL.2011.218
Non-Definability Results for Randomised First-Order Logic

Authors: Kord Eickmeyer

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

Abstract
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].
Cite as

Kord Eickmeyer. Non-Definability Results for Randomised First-Order Logic. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 218-232, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{eickmeyer:LIPIcs.CSL.2011.218,
  author =	{Eickmeyer, Kord},
  title =	{{Non-Definability Results for Randomised First-Order Logic}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{218--232},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.218},
  URN =		{urn:nbn:de:0030-drops-32333},
  doi =		{10.4230/LIPIcs.CSL.2011.218},
  annote =	{Keywords: descriptive complexity, randomised logics, derandomisation}
}
  • Refine by Type
  • 7 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2017
  • 1 2016
  • 1 2011

  • Refine by Author
  • 3 Eickmeyer, Kord
  • 1 Bonnet, Édouard
  • 1 Carenini, Gaia
  • 1 Colin de Verdière, Éric
  • 1 Duron, Julien
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Combinatorics
  • 1 Theory of computation
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Finite Model Theory
  • Show More...

  • Refine by Keyword
  • 1 Adjacency labeling
  • 1 Automatability
  • 1 Dominating Set
  • 1 Graph Structure Theory
  • 1 Kernelization
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact