Pith. sign in

REVIEW 1 major objections 3 minor 25 references

A dynamic data structure answers distance-r domination and independence queries on sparse graphs in polylog amortized time per edge update, and can report the actual dominating set when one exists.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 04:55 UTC pith:55I2TKB5

load-bearing objection Major progress on a twelve-year-open problem, but as written the fraternal augmentation maintenance in Claim 6.5 has a genuine deletion-triggered gap that undermines the main theorems until fixed. the 1 major comments →

arxiv 2607.22384 v1 pith:55I2TKB5 submitted 2026-07-24 cs.DS

Dynamic domination and independence in sparse graphs

Bart{\l}omiej Bosek , Wojciech Nadara , Micha{\l} Pilipczuk , Anna Zych-Pawlewicz This is my paper
classification cs.DS MSC 68R1005C85
keywords dynamic graph data structuresbounded expansiondistance-r dominating setdistance-r independent setfraternal augmentationdegenerate graphsdominating set approximationfingerprint retrieval
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper aims to prove that two canonical local search problems—whether a sparse dynamic graph has a distance-r dominating set of size k, and whether it has a distance-r independent set of size k—can be solved with polylogarithmic amortized update time under edge insertions and deletions. Bounded expansion classes, the sparse graph families targeted here, include bounded-degree, planar, and minor-closed graphs. If correct, this is the first polylog-time fully dynamic maintenance of an ∃∀ first-order query on such classes, a gap that has stood open for over a decade. The data structures are randomized, with error bounded by ε against an oblivious adversary, and the dominating-set variant reports an actual set. The paper also gives a simplified structure for ordinary domination in d-degenerate graphs and a (4d+1)²-approximation of the domination number with expected polylog update time.

Core claim

The central claim is that on any fixed bounded-expansion class, distance-r dominating sets of size k and distance-r independent sets of size k admit randomized fully dynamic data structures with amortized update time log^{O_{C,r,k}(1)} n · log(1/ε) and correctness probability 1−ε. The key reduction is algorithmic: a bounded-round candidate–witness exploration, called progressive exploration, shows that both problems reduce to two primitive queries—find a vertex close to a small set within given radii, and find a vertex far from a small set. Close-vertex queries are implemented through rooted homomorphism counting enhanced with a fingerprint-retrieval technique that converts counts into repor

What carries the argument

Two mechanisms carry the argument. First, the semi-ladder and ladder exploration algorithms: iterative candidate–witness procedures that terminate in a constant number of rounds on bounded-expansion classes, each round reducing to a constant number of nearVertex and farVertex queries on small sets. Second, the fraternal augmentation: a constant-degree, labelled, directed supergraph built level by level in which every pair of vertices at distance at most r is connected by a unique oriented shortcut whose edge labels and lengths form a small pattern. Farness from a vertex can then be expressed as an inclusion–exclusion sum over homomorphism counts from finitely many fixed shortcut patterns. Ne

Load-bearing premise

The entire polylog bound rests on the claim that the iterated fraternal augmentation can be maintained with amortized O_{C,r}(log^{r-1} n) structural changes per update by cascading bounded-outdegree orientation updates level by level; if deletions ever force more than polylog reorientations at one level, or a transient intermediate graph leaves the bounded-expansion class, the shortcut patterns used by farVertex queries cease to be faithful and the polylog guarantee breaks.

What would settle it

Take a bounded-expansion graph—say a constant-degree grid or bounded-degree expander—and run the proposed augmentation maintenance under adversarial edge insertions and deletions, instrumenting each level to count reorientations per update and verifying after every batch that the maintained decorated supergraph is a faithful augmentation (every length-≤r path has a shortcut and every shortcut corresponds to a real path). A single amortized violation—any level with ω(log^{r-1} n) reorientations per update, or a farVertex query that returns a vertex actually within distance r of S—would refute t

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • If the central claim is correct, both distance-r domination and distance-r independence can be maintained exactly, with reporting, in polylog amortized update time on every fixed bounded-expansion class.
  • It closes a decade-old gap between dynamically counting small subgraph patterns and actually returning an example mapping, with only a log n · log(1/ε) overhead over counting-only structures.
  • For distance-1 domination, the assumption can be relaxed to bounded degeneracy: updates run in 2^{k^{O(d)}} · log³ n · log(1/ε), showing that the full bounded-expansion machinery is unnecessary for the radius-1 case.
  • It also yields the first dynamic constant-factor approximation of the domination number in d-degenerate graphs, maintaining a dominating set of size at most (4d+1)² times the optimum with expected amortized d^{O(1)} log n update time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The far-vertex machinery—maintaining the fraternal augmentation—is the only step that currently blocks lifting these bounds from bounded expansion to nowhere-dense classes; if the augmentation cascade could be amortized on nowhere-dense classes, the same argument would plausibly give n^{o(1)}-type update times.
  • The fingerprint-retrieval conversion from counting to example-reporting looks like a general template: any dynamic counting structure whose homomorphism, subgraph, or induced-subgraph counts can be weighted can likely be upgraded to report witnesses at polylog overhead.
  • A practical stress test of the paper's key invariant would be to instrument the augmentation cascade under adversarial edge deletions: if any level ever suffers superlogarithmic reorientations in an amortized sequence, or an intermediate graph leaves the bounded-expansion class, the shortcut patterns used by farVertex queries would silently become unfaithful.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 3 minor

Summary. The paper proposes randomized fully dynamic data structures for Distance-r Dominating Set (outputting a witnessing set) and Distance-r Independent Set (existence only) on any fixed bounded-expansion class, with amortized polylog n · log(1/eps) update/query time. The reduction chain is explicit: the progressive-exploration algorithms of Fabiański et al. are reduced (Section 4) to nearVertex and farVertex queries; nearVertex is implemented through Dvořák–Tůma dynamic counting plus fingerprint retrieval (Theorems 6.1, 5.8, Lemma 5.2); farVertex is implemented through a dynamically maintained iterated fraternal augmentation (Lemma 6.4) and an Inclusion–Exclusion formula over shortcut patterns (Lemma 6.9). The paper also gives a simpler r=1 implementation for d-degenerate graphs (Theorem 1.3, Sections 7) and a dynamic O(d^2)-approximation for minimum dominating set (Theorem 1.4, Section 8).

Significance. If the main theorems are correct, this is a substantial advance: it closes a 12-year gap since Dvořák–Tůma by giving the first polylog fully dynamic maintenance of ∃∀ FO-definable problems (domination and independence) on bounded-expansion classes, and it resolves the example-reporting question raised in [9] via the fingerprint retrieval toolbox. The paper is unusually explicit about its reduction chain, the probability analysis in Lemma 5.2 is detailed and sound, and the weighted-counting appendix is a useful contribution. However, the central claim rests on the dynamic correctness of the fraternal augmentation maintenance, and that is exactly where I find a load-bearing gap (see Major Comment 1).

major comments (1)
  1. [§6.2, Claim 6.5 (proof of Lemma 6.4)] Claim 6.5 maintains counters cnt_{e,i} only for edges e that are currently in G'_{i+1}. This misses fraternal edges that become necessary after a deletion. Concretely, let u,w,v form a triangle with uv in G_1 and w->u, w->v in D_1. At construction time uv is not placed in G'_2 because uv is already in G_1. Now delete uv from G, hence from D_1. The fork w->u, w->v is untouched, so the update procedure has no event that increments a counter for uv, and uv is never added to G'_2 even though it is now required. Thus D_2 is not a faithful (Λ,2)-augmentation: the path u-w-v has no shortcut, violating (A4) and making Claim 6.6 false. Since Claim 6.10, Lemma 6.9, and Theorem 6.7 all rest on faithfulness, farVertex can return a false positive and the polylog guarantee of Theorem 1.1 breaks. The issue is fixable, e.g. by maintaining counters for all potential fraternal pairs satisfying the length
minor comments (3)
  1. [§5.2, Theorem 5.8] The displayed bound 'O_C(log^{O_{B⟨x⟩,Σ}(1)} log n)' looks like a typo; it should presumably read (log n)^{O_{B,Σ}(1)} or a similar polylogarithmic expression.
  2. [§2.3 and Definition 6.3] Shortcut indices are written both as 0=α_1<... and as 0=α_0<... (see also Figure 2). Please harmonize the indexing with Definition 6.3, where α_0=0.
  3. [Theorem 7.6] The stated amortized complexity includes a factor 2^{|S|}, but |S| is a query parameter. Updates cannot depend on |S| unless a maximum |S| is fixed in advance. The statement should clarify whether |S| is a fixed bound or whether the bound is per query.

Circularity Check

0 steps flagged

No significant circularity: the main derivation rests on externally published, parameter-free results and on constructions proved inside the paper, not on fitting or self-definition.

full rationale

The paper's main theorems combine three independent ingredients rather than reducing to their own inputs. First, the progressive-exploration termination bounds (Theorems 2.1, 4.1, 4.3, 4.7) are imported from the prior static work [10]; although one coauthor (Pilipczuk) overlaps, [10] is an externally published, parameter-free theorem whose assumptions do not include the dynamic data structure claimed here, so it is independent support under the review rules. Second, the near-vertex and far-vertex machinery is mostly proved in the paper: the homomorphism reduction (Claim 2.4), the fingerprint retrieval lemma (Lemma 5.2, inspired but not borrowed from [18,19]), the weighted counting extension (Theorem 5.6 and Section A), and the Inclusion-Exclusion shortcut counting (Lemma 6.9, Claims 6.10-6.12) are all derived explicitly. Third, the dynamic maintenance of faithful fraternal augmentations (Lemma 6.4 and Claim 6.5) is built on the external Brodal-Fagerberg orientation data structure [3] and on sparsity lemmas proved in the text. The load-bearing reductions do not equate a prediction with a fitted parameter or define an output in terms of itself. The proof of Claim 6.5 is admittedly sketched, and the deletion-triggered counterexample suggested by the reviewer is a possible correctness gap in the maintenance of fraternal edges after deletions; however, that is a question of soundness of a claimed construction, not circularity, because the faithful augmentation is an output of the construction rather than an assumption reintroduced as a result. Therefore no circular step is identified and the circularity score is 0.

Axiom & Free-Parameter Ledger

1 free parameters · 8 axioms · 0 invented entities

The central claims rest on a stack of prior theorems, three of which come from the same research group ([10] and [18,19]) — those supply the round bounds and the fingerprint intuition; the rest are standard Sparsity and dynamic-data-structure results ([3,8,9,21,1]). No data-fitting free parameters exist (the big-O constants are structural). The strongest modeling assumptions are: (i) the at-all-times class membership promise, and (ii) the uniform, history-independent validity of the amortized cascade in the augmentation tower. The paper is transparent about this dependency chain, which is normal for this literature but means a reader must trust three black boxes: [10]'s termination theorems, [9]'s counting structure, and the Assadi–Solomon packing structure.

free parameters (1)
  • hidden class-dependent constants (sli_r(C), p, ℓ, Δ_r, d_1..d_r)
    The O_{C,r,k}(·) guarantees hide constants derived from [10]'s semi-ladder index and the fraternal augmentation degrees; these are structural bounds, not fitted to data, but they are not explicitly computed, which matters if the result is to be implemented.
axioms (8)
  • domain assumption The maintained graph G belongs to C at all times (promise), for a fixed bounded-expansion class C with known ∇_i(C) bounds.
    Used throughout (Theorems 1.1–1.4 and Lemmas 3.2, 3.4, 6.4); if the promise is violated during update streams the data structures have no correctness guarantee.
  • standard math Theorem 4.1 ([10, Lemma 29]): sli_r(C) is finite for bounded-expansion C; Theorem 4.2 ([10, Lemma 33]) bounds sli_1 by 3t for K_{t,t}-free graphs.
    Bounds the number of semi-ladder rounds, hence the size ℓ of W in candidateDom and the overall query counts. Cited, not reproven; involves deep Sparsity theory (flatness).
  • standard math Theorem 4.7 ([10]): ladder algorithm for Distance-r Independent Set is correct and terminates in O_{C,r,k}(1) rounds with p, ℓ ∈ O_{C,r,k}(1).
    Basis of Theorem 1.2; correctness of the independence-side answer is imported from the cited paper.
  • standard math Theorem 5.1 ([9]): dynamic counting of |F(H,G)| for F ∈ {Hom,Sub,ISub} on bounded-expansion classes with O(log^h n) updates, and its robustness to vertex/edge colors and rooting.
    The near-vertex query and the homomorphism-count machinery (Theorem 5.8, Lemma 6.8) build on this.
  • standard math Theorem 3.5 (Brodal–Fagerberg) dynamic d-orientation with O(1) insertions, O(d+log n) deletions, O(log n) reorientations.
    Used for the augmentation towers (Lemma 6.4), the degenerate-case toolkit (Section 7), and the approximation structure (Section 8).
  • standard math Theorem 8.7 (Assadi–Solomon) fully dynamic maximal packing in arity-Δ set systems in O(Δ²) expected amortized time.
    The approximation data structure of Theorem 1.4 stores its dominating set as a maximal packing; if this structure failed, the O(d²) approximation would not be maintained.
  • standard math Lemma 3.4/Theorem 3.3: fraternal augmentation and congested shallow minors preserve bounded expansion (from Sparsity theory [21]).
    Ensures the iterated augmentation classes C_i have bounded expansion, and that pendant extensions (Lemma 3.2) stay in a bounded-expansion class; used in Lemma 6.4, Lemma 5.7, Theorem 6.7.
  • standard math Word-RAM model with O(log n) words; all maintained integer quantities (weights, homomorphism counts) polynomially bounded in n.
    Section 3.2; constant-time arithmetic is assumed; the vertex-label weights used in fingerprint retrieval are ≤ n so products stay polynomial for fixed H.

pith-pipeline@v1.3.0-alltime-deepseek · 60060 in / 21780 out tokens · 229347 ms · 2026-08-01T04:55:58.437776+00:00 · methodology

0 comments
read the original abstract

Let $\mathscr{C}$ be a class of graphs of bounded expansion and $r,k\in \mathbb{N}$ be fixed. We give a dynamic data structure that for a given dynamic graph $G$, updated by edge insertions and deletions subject to the promise that $G\in \mathscr{C}$ at all times, maintains the answer to the following two queries: (a) Does $G$ contain a distance-$r$ dominating set of size $k$? (b) Does $G$ contain a distance-$r$ independent set of size $k$? The data structure is randomized with error probability bounded by $\varepsilon$, for a parameter $\varepsilon>0$ fixed upon the initialization. The amortized update time is $\log^c n\cdot \log \frac{1}{\varepsilon}$, where $n$ is the vertex count of $G$ and $c$ is a constant that depends only on $r$, $k$, and $\mathscr{C}$. In the case of the first query, the data structure can also output a distance-$r$ dominating set of size $k$, if existent. We also prove that when $r=1$, our data structure for the dominating set query can be implemented even if we only assume that the maintained graph $G$ has degeneracy bounded by a constant $d$, yielding a simpler data structure with an improved amortized update time of $2^{k^{{\cal O}(d)}}\cdot \log^3 n\cdot \log \frac{1}{\varepsilon}$. Finally, we prove that in graphs of degeneracy at most $d$, one can maintain an ${\cal O}(d^2)$-approximation of the minimum size of a (distance-$1$) dominating set with amortized expected update time $d^{{\cal O}(1)}\cdot \log n$.

Figures

Figures reproduced from arXiv: 2607.22384 by Anna Zych-Pawlewicz, Bart{\l}omiej Bosek, Micha{\l} Pilipczuk, Wojciech Nadara.

Figure 1
Figure 1. Figure 1: Graph Hρ in Claim 2.4. It is constructed from vertex x and vertices z1, . . . , zℓ by connecting x with zi by a path of length ρ(i), for each i ∈ {1, . . . , ℓ}. Theorem 2.3 ([9]). Fix a bounded expansion class C , graph H, and F ∈ {Hom, Sub,ISub}. Then there is a data structure that for a dynamic graph G on n vertices, guaranteed to belong to C at all times, maintains the value |F(H, G)| with amortized up… view at source ↗
Figure 2
Figure 2. Figure 2: An a-b-path with a shortcut. The directed paths Q, R of the shortcut are resp. red and blue. An important idea in the work of Dvořák and Tůma [9] is that the sequence of fraternal augmentations described above can be maintained in the dynamic setting with amortized update time OC ,r(logr n). The key component here is the classic data structure of Brodal and Fagerberg [3], which can be used to maintain the … view at source ↗
Figure 3
Figure 3. Figure 3: Example graph HΓ constructed for a set Γ ⊆ Π of size 5. Every pair (red path, blue path) represents a shortcut with some pattern π ∈ Γ. Note that both the red edges and the blue edges are decorated with {1, . . . , d} × {1, . . . , r} (not depicted). In our argumentation we take an extra mile to clarify that the combinatorial argument behind the approximation guarantee is in fact more general, as it extend… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 2 linked inside Pith

  1. [1]

    Fully dynamic set cover via hypergraph maximal matching: An optimal approximation through a local approach

    Sepehr Assadi and Shay Solomon. Fully dynamic set cover via hypergraph maximal matching: An optimal approximation through a local approach. In29th Annual European Symposium on Algorithms, ESA 2021, volume 204 ofLIPIcs, pages 8:1–8:18. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2021

    2021

  2. [2]

    Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A

    Lélia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. What can be computed locally revisited: First-order logic on sparse graphs in distributed computing. In58th Annual ACM Symposium on Theory of Computing, STOC 2026, pages 1397–1408. ACM, 2026

    2026

  3. [3]

    Dynamic representation of sparse graphs

    Gerth Stølting Brodal and Rolf Fagerberg. Dynamic representation of sparse graphs. In6th Inter- national Workshop on Algorithms and Data Structures, W ADS 1999, volume 1663 ofLecture Notes in Computer Science, pages 342–351. Springer, 1999

    1999

  4. [4]

    Domination problems in nowhere-dense classes

    Anuj Dawar and Stephan Kreutzer. Domination problems in nowhere-dense classes. In29th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, volume 4 ofLIPIcs, pages 157–168. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2009

    2009

  5. [5]

    Constant-factor approximation of the domination number in sparse graphs.Euro- pean Journal of Combinatorics, 34(5):833–840, 2013

    Zdenek Dvořák. Constant-factor approximation of the domination number in sparse graphs.Euro- pean Journal of Combinatorics, 34(5):833–840, 2013

    2013

  6. [6]

    Approximation metatheorems for classes with bounded expansion

    Zdenek Dvořák. Approximation metatheorems for classes with bounded expansion. In18th Scan- dinavian Symposium and Workshops on Algorithm Theory, SW AT 2022, volume 227 ofLIPIcs, pages 22:1–22:17. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2022

    2022

  7. [7]

    Testing first-order properties for subclasses of sparse graphs.Journal of the ACM, 60(5):36:1–36:24, 2013

    Zdenek Dvořák, Daniel Král’, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs.Journal of the ACM, 60(5):36:1–36:24, 2013

    2013

  8. [8]

    A dynamic data structure for counting subgraphs in sparse graphs

    Zdenek Dvořák and Vojtech Tůma. A dynamic data structure for counting subgraphs in sparse graphs. CoRR, abs/1209.0375, 2012

    Pith/arXiv arXiv 2012

  9. [9]

    A dynamic data structure for counting subgraphs in sparse graphs

    Zdenek Dvořák and Vojtech Tůma. A dynamic data structure for counting subgraphs in sparse graphs. In13th International Symposium on Algorithms and Data Structures, W ADS 2013, volume 8037 ofLec- ture Notes in Computer Science, pages 304–315. Springer, 2013

    2013

  10. [10]

    Progressive algo- rithms for domination and independence.CoRR, abs/1811.06799, 2018

    Grzegorz Fabiański, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. Progressive algo- rithms for domination and independence.CoRR, abs/1811.06799, 2018

    Pith/arXiv arXiv 2018

  11. [11]

    Progressive algo- rithms for domination and independence

    Grzegorz Fabiański, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. Progressive algo- rithms for domination and independence. In36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, volume 126 ofLIPIcs, pages 27:1–27:16. Schloss Dagstuhl — Leibniz- Zentrum für Informatik, 2019

    2019

  12. [12]

    Methods for algorithmic meta theorems.Model Theoretic Meth- ods in Finite Combinatorics, 558:181–206, 2011

    Martin Grohe and Stephan Kreutzer. Methods for algorithmic meta theorems.Model Theoretic Meth- ods in Finite Combinatorics, 558:181–206, 2011. 52

    2011

  13. [13]

    Deciding first-order properties of nowhere dense graphs.Journal of the ACM, 64(3):17:1–17:32, 2017

    Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs.Journal of the ACM, 64(3):17:1–17:32, 2017

    2017

  14. [14]

    First-order query evaluation with cardinality conditions

    Martin Grohe and Nicole Schweikardt. First-order query evaluation with cardinality conditions. In 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2018, pages 253–266. ACM, 2018

    2018

  15. [15]

    First-order queries on classes of structures with bounded expan- sion.Logical Methods in Computer Science, 16(1), 2020

    Wojciech Kazana and Luc Segoufin. First-order queries on classes of structures with bounded expan- sion.Logical Methods in Computer Science, 16(1), 2020

    2020

  16. [16]

    Oracles for bounded-length shortest paths in planar graphs

    Łukasz Kowalik and Maciej Kurowski. Oracles for bounded-length shortest paths in planar graphs. ACM Transactions on Algorithms, 2(3):335–363, 2006

    2006

  17. [17]

    Minimum dominating set approximation in graphs of bounded arboricity

    Christoph Lenzen and Roger Wattenhofer. Minimum dominating set approximation in graphs of bounded arboricity. In24th International Symposium on Distributed Computing, DISC 2010, volume 6343 ofLecture Notes in Computer Science, pages 510–524. Springer, 2010

    2010

  18. [18]

    Parameterized dynamic data struc- ture for Split Completion

    Konrad Majewski, Michał Pilipczuk, and Anna Zych-Pawlewicz. Parameterized dynamic data struc- ture for Split Completion. In32nd Annual European Symposium on Algorithms, ESA 2024, volume 308 ofLIPIcs, pages 87:1–87:17. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2024

    2024

  19. [19]

    Computing treedepth in polynomial space and linear FPT time

    Wojciech Nadara, Michał Pilipczuk, and Marcin Smulewicz. Computing treedepth in polynomial space and linear FPT time. In30th Annual European Symposium on Algorithms, ESA 2022, volume 244 ofLIPIcs, pages 79:1–79:14. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2022

    2022

  20. [20]

    Grad and classes with bounded expansion II

    Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion II. Algo- rithmic aspects.European Journal of Combinatorics, 29(3):777–791, 2008

    2008

  21. [21]

    Springer, 2012

    Jaroslav Nešetřil and Patrice Ossona de Mendez.Sparsity — Graphs, Structures, and Algorithms, vol- ume 28 ofAlgorithms and combinatorics. Springer, 2012

    2012

  22. [22]

    Sparsity

    Marcin Pilipczuk, Michał Pilipczuk, and Sebastian Siebertz. Lecture notes for the course “Sparsity” given at Faculty of Mathematics, Informatics, and Mechanics of the University of Warsaw, Winter semesters 2017/18 and 2019/20. Available online at https://www.mimuw.edu.pl/ mp248287/sparsity2

    2017

  23. [23]

    Parameterized circuit complexity of model-checking on sparse structures

    Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. Parameterized circuit complexity of model-checking on sparse structures. In33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, pages 789–798. ACM, 2018

    2018

  24. [24]

    Enumeration for FO queries over nowhere dense graphs.Journal of the ACM, 69(3):22:1–22:37, 2022

    Nicole Schweikardt, Luc Segoufin, and Alexandre Vigny. Enumeration for FO queries over nowhere dense graphs.Journal of the ACM, 69(3):22:1–22:37, 2022

    2022

  25. [25]

    Aggregate queries on sparse databases

    Szymon Toruńczyk. Aggregate queries on sparse databases. In39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, pages 427–443. ACM, 2020. A The proof of Theorem 5.6 The proof of Theorem 5.6 is heavily based on the proof of its original unweighted version from [8]. (Note that [9] is the conference version of this work, throu...

    2020