Pith. sign in

REVIEW 1 major objections 8 minor 33 references

FO Value Discovery and Partial Vertex Cover Discovery

T0 review · 1 major / 8 minor · reviewed 2026-07-08 · glm-5.2

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

Pith's one-line read Moving tokens to cover edges: a logical framework for optimization under a movement budget

desk verdict Solid paper introducing a clean optimization framework for solution discovery with concrete hardness results; one minor proof imprecision that doesn't undermine the main theorems. read the letter →

arxiv 2607.06446 v1 pith:EVBOFN6N submitted 2026-07-07 cs.DM cs.LOmath.CO

Enna Gerhard , Stephanie Maaz , Pascale Schott , Sebastian Siebertz , Jan Wodkte This is my paper · ORCID
classification cs.DMcs.LOmath.CO
keywords solutiondiscoverytokenslidingpartialvertexcoverfirst-orderlogicparameterizedcomplexitygraphclassesfixed-parametertractabilitymeta-theorem
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper introduces FO Cost-Value Decision, a framework that extends first-order logic model-checking to handle quantitative optimization: vertices carry both costs and values, and first-order formulas define correction terms that adjust the value of a selected tuple based on structural patterns (such as adjacency between chosen vertices). The motivating application is Partial Vertex Cover Discovery, where k tokens start at initial positions on a graph and must be slid within a movement budget b to cover at least t edges; the edge-counting objective is inherently non-additive because edges with both endpoints selected are double-counted. The central meta-theorem (Theorem 6) shows that FO Cost-Value Decision is fixed-parameter tractable on any graph class satisfying two conditions: efficient local FO cost-value decision (solving the problem within bounded-radius neighborhoods) and efficient anchored weighted multicolored distance independence (a packing problem that selects far-apart local candidates while respecting cost and value bounds). The authors verify these two conditions for classes of locally structurally bounded expansion, locally bounded cliquewidth, and, for the existential fragment, monadically stable classes. As a consequence, Partial Vertex Cover Discovery is FPT on all these graph classes, parameterized by the number of tokens k. The paper also establishes hardness boundaries: Partial Vertex Cover Discovery is W[1]-hard parameterized by k+b (so the movement budget alone does not help), and Vertex Cover Discovery is NP-hard on planar graphs and W[1]-hard parameterized by cutwidth or clique cover number. A dedicated FPT algorithm for Partial Vertex Cover Discovery on d-degenerate graphs parameterized by k+d is also given, using universal-set splitters to reduce to a group knapsack problem.

What carries the argument

FO Cost-Value Decision framework; anchored weighted multicolored distance-r independence; Gaifman locality decomposition; universal-set splitters for degenerate graphs; LinEMSOL optimization on bounded cliquewidth; quasi-bounded-size bounded-shrubdepth decompositions for monadically stable classes

What would settle it

Exhibit a graph class of locally bounded cliquewidth (or a monadically stable class) on which the anchored weighted multicolored distance-r independence problem is W[1]-hard, which would collapse the meta-theorem's applicability to that class.

Watch

Extended reading notes

Core claim

The paper identifies that quantitative discovery problems with non-additive objectives—where the value of a selected vertex set depends on structural patterns among the chosen vertices, not just per-vertex weights—can be captured by first-order value expressions combining unary weights with FO-definable correction terms. The key algorithmic insight is that Gaifman locality for first-order logic decomposes any such optimization into local computations on bounded-radius neighborhoods, followed by a global packing step (anchored weighted multicolored distance independence) that selects mutually far-apart local candidates while aggregating their costs and values. This two-ingredient recipe is a

Load-bearing premise

The meta-theorem's tractability depends on the anchored weighted multicolored distance-r independence problem being FPT on the target graph classes. The paper treats this as a mild extension of ordinary distance-based packing and argues it reduces to standard FO model-checking machinery, but if this reduction is more delicate than claimed—or fails on the classes at the boundary such as monadically stable graphs—the main tractability results would not hold.

Editorial extensions

If this is right

  • Any graph class where local FO model-checking and distance-based packing are both tractable inherits FPT for weighted FO optimization with correction terms, providing a template for extending logical meta-theorems beyond Boolean feasibility to quantitative objectives.
  • Partial Vertex Cover Discovery is tractable on common sparse and dense graph classes (bounded expansion, bounded cliquewidth, monadically stable) parameterized only by the number of tokens, making it accessible on graphs where the general k+b parameterization is W[1]-hard.
  • The separation between W[1]-hardness for k+b and FPT for k on structurally restricted classes clarifies that graph structure, not movement budget size, is the algorithmic lever for discovery problems.
  • The framework can model discovery variants of any problem whose objective decomposes as a sum of unary vertex weights plus an FO-definable correction, including problems beyond vertex cover such as dominating-set-quality or budgeted subgraph optimization.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If full FO Cost-Value Decision is eventually proven FPT on monadically stable classes (as the authors expect), the existential-fragment restriction in Theorem 10 would become unnecessary, unifying all the monadic-stability results.
  • The anchored distance-independence formulation is strictly weaker than full FO model-checking, so the meta-theorem could in principle yield tractability on classes where full model-checking is hard, provided the packing problem remains tractable—a direction the authors note but do not exploit.
  • The universal-set technique for d-degenerate graphs suggests that similar derandomization or covering arguments could yield dedicated FPT algorithms for other non-additive discovery problems on sparse graphs without invoking the full logical machinery.
  • The NP-hardness on planar graphs for Vertex Cover Discovery, combined with FPT on bounded-treewidth classes, implies that the problem's hardness is tied to planar graph structure in a way that standard sparsity-based meta-theorems do not resolve.
Share X Bluesky LinkedIn Reddit HN

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 / 8 minor

Summary. This paper introduces FO Cost-Value Decision, a logical optimization framework that extends Boolean FO solution discovery to quantitative objectives where the value of a selected tuple is given by unary vertex weights plus first-order definable correction terms. The framework is motivated by and applied to Partial Vertex Cover Discovery, where the covered-edge count decomposes as a sum of degrees minus an adjacency-pattern correction. The central result is a conditional meta-theorem (Theorem 6) reducing FPT tractability of FO Cost-Value Decision to two ingredients: efficient Local FO Cost-Value Decision and efficient anchored weighted multicolored distance-r independence. The authors verify these ingredients on several graph classes (locally structurally bounded expansion, locally bounded cliquewidth, monadically stable), yielding FPT results for Partial Vertex Cover Discovery. The paper also proves W[1]-hardness for Partial Vertex Cover Discovery parameterized by k+b, NP-hardness and W[1]-hardness for Vertex Cover Discovery on planar graphs and with respect to cutwidth and clique cover number, and gives a dedicated FPT algorithm on d-degenerate graphs parameterized by k+d.

Significance. The paper makes a solid contribution by identifying and formalizing a natural quantitative gap in the solution discovery framework: many discovery objectives (exemplified by Partial Vertex Cover) involve correction terms that are not purely unary but depend on the adjacency pattern of the selected tuple. The FO Cost-Value Decision framework captures this cleanly, and the meta-theorem (Theorem 6) is a well-structured reduction to two algorithmic ingredients that are then verified on standard graph classes. The hardness results are explicit and cover complementary parameters. The FPT algorithm for d-degenerate graphs (Theorem 12) via universal sets is a nice self-contained result. The proofs build on established model-checking machinery (Gaifman locality via Theorem 19, LinEMSOL, aggregate queries on bounded expansion, monadic stability decompositions) and the reductions are traced carefully. The paper provides falsifiable complexity-theoretic predictions and the main meta-theorem is stated with clearly identified assumptions.

major comments (1)
  1. [Lemma 33 (p. 24)] The proof states: 'It follows from Theorem 10, since the multicolored distance-r independence condition is FO definable.' However, the anchored version (Definition 4) has candidates that are abstract objects (triples (C, a, q') in the proof of Theorem 6) with an anchor map to V(G), and a single anchor vertex can host multiple candidates with different (cost, profit) pairs. This means the problem does not directly reduce to an existential FO Cost-Value Decision instance on G, because FO Cost-Value Decision assumes a single unary cost and value per vertex per coordinate. The correct approach—described informally in Remark 5—is to use FO model checking on G to select anchor vertices satisfying the pairwise distance constraint, then handle the cost-profit selection among candidates sharing an anchor via dynamic programming. The remark sketches this but the lemma does not formalize it. Since:
minor comments (8)
  1. [Theorem 12 (p. 8)] The dependency on the meta-theorem of Grobler et al. [14] for the unary-weighted FO Value Discovery subproblem is stated without elaboration. A one-sentence explanation of how the Group Knapsack reduction works in the discovery setting would help the reader.
  2. [Section 3.2 (p. 9–12)] The reduction from Circulating Orientation to Vertex Cover Discovery is intricate. The budget-tightness argument (p. 11, 'Any moving pattern besides the one described above will take an additional step') is stated somewhat informally. A brief remark formalizing why no alternative filling pattern can stay within budget would strengthen the proof.
  3. [Figure 1 (p. 10)] The figure caption and the text reference vertices 'ce' and 'de' in the cycle description ('edges {pe_1, qe_1} and {ce_{w(e)}, de_{w(e)}}'), but ce and de are not defined in the construction. These appear to be a typo for pe and qe.
  4. [Lemma 28 (p. 21)] The statement 'Classes of locally structurally bounded expansion are monadically stable' is used to defer to Lemma 33. A brief justification or citation for this containment would be helpful, as it is not immediate to all readers.
  5. [Theorem 32 (p. 23–24)] The theorem is labeled 'Algorithmic version of [13]' but the text explains that the algorithmicity requires substituting ingredients from [7] and [13] into the decomposition construction of [2]. The reader would benefit from a sentence clarifying whether this substitution is routine or whether additional work is needed.
  6. [Definition 1 (p. 2)] The partition assumption on the formulas φ_1,...,φ_m is stated as 'notational only' via refinement into the Boolean partition. It would help to note that m can be exponential in k and the formula size, and that this is absorbed into the parameter.
  7. [General] The paper uses 'efficient' as a prefix for several properties (Definitions 3, 4, 22) to mean 'fixed-parameter tractable.' A footnote or remark clarifying this convention on first use would help.
  8. [References [11] and [12]] These are identical citations (Gajarský et al., ACM TOCL 2020). One should be removed.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and the constructive assessment. The referee raises one major comment concerning the proof of Lemma 33, which correctly identifies a gap between the one-line argument currently in the manuscript and the actual algorithmic content needed. We agree with the referee's observation and will revise the lemma accordingly.

read point-by-point responses

  1. Referee: [Lemma 33 (p. 24)] The proof states: 'It follows from Theorem 10, since the multicolored distance-r independence condition is FO definable.' However, the anchored version (Definition 4) has candidates that are abstract objects (triples (C, a, q') in the proof of Theorem 6) with an anchor map to V(G), and a single anchor vertex can host multiple candidates with different (cost, profit) pairs. This means the problem does not directly reduce to an existential FO Cost-Value Decision instance on G, because FO Cost-Value Decision assumes a single unary cost and value per vertex per coordinate. The correct approach—described informally in Remark 5—is to use FO model checking on G to select anchor vertices satisfying the pairwise distance constraint, then handle the cost-profit selection among candidates sharing an anchor via dynamic programming. The remark sketches this but the lemma does not.

    Authors: The referee is correct. The one-line proof of Lemma 33 is insufficient as written. The issue is precisely the one identified: the anchored problem (Definition 4) has abstract candidate objects (triples (C, a, q') in the proof of Theorem 6) that do not correspond one-to-one with vertices of G, so the problem does not reduce directly to an existential FO Cost-Value Decision instance on G. The reduction described informally in Remark 5—adding unary predicates to G recording which candidates may use a given vertex as their anchor, together with the relevant local cost and profit information, then using FO model checking to select anchors satisfying the pairwise distance constraint, and finally handling the cost-profit bookkeeping among candidates sharing an anchor via dynamic programming—is the correct approach. We will revise Lemma 33 to formalize this two-step argument explicitly: (1) FO model checking on the monadically stable class (preserved under the bounded unary expansion recording candidate information) selects anchor vertices satisfying the pairwise distance-r constraint; (2) since the budget B is polynomially bounded and the number of colors p is a parameter, the cost-profit selection among candidates sharing an anchor is handled by standard dynamic programming. We note that this does not change any of the results that depend on Lemma 33 (Theorem 11, Lemma 28, and the consequent Theorems 7 and 9), as the algorithmic content is exactly that sketched in Remark 5; it only formalizes what the lemma currently leaves implicit. revision: yes

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity found; derivation chain is self-contained against external benchmarks.

full rationale

The paper's central meta-theorem (Theorem 6) is proved via a standard Gaifman-locality decomposition, assuming two independently verifiable ingredients (Definitions 3 and 4). These ingredients are then verified for specific graph classes using external results: the efficient reversal theorem of Dreier–Gajarský–Pilipczuk [8], aggregate-query evaluation of Toruńczyk [32], LinEMSOL optimization of Courcelle–Makowsky–Rotics [4], and FO model checking on monadically stable classes [7, 9]. No ingredient is defined in terms of the conclusion it supports. The one potentially circular-looking step is Lemma 33, which derives anchored distance-independence on monadically stable classes from Theorem 10; but Theorem 10 is proved independently via quasi-bounded-size bounded-shrubdepth decompositions (Theorem 32) and Lemma 26, with no dependency on Theorem 6 or Lemma 33. The self-citations (references [1], [10], [14], [35]) are used for problem context and prior solution-discovery frameworks, not as load-bearing premises for the main technical results. The paper contains no fitted parameters, no ansatz smuggled through self-citation, and no renaming of known results as new predictions. The minor imprecision in Lemma 33's proof (the anchored reduction) is a correctness concern, not a circularity concern, as Remark 5 provides the missing argument. Score 1 reflects the presence of self-citations that are non-load-bearing for the central derivation.

Assumptions & free parameters 0 free parameters · 5 assumptions · 2 invented entities

The paper relies on standard mathematical axioms (Gaifman locality, LinEMSOL) and domain assumptions (algorithmic Flipper games). It introduces two new problem definitions (FO Cost-Value Decision, anchored distance independence) which are the main contributions, not ad hoc inventions. No free parameters are fitted.

assumptions (5)
  • standard math Gaifman locality theorem for first-order logic (Theorem 19)
    Used in the proof of the main meta-theorem (Theorem 6) to decompose FO formulas into local and distance-independent parts.
  • standard math LinEMSOL optimization theorem on graphs of bounded cliquewidth
    Used in Lemma 29 to prove efficient weighted FO tuple optimization on bounded cliquewidth classes.
  • standard math Efficient reversal theorem for transductions of sparse graph classes
    Used in Lemma 26 to prove efficient weighted FO tuple optimization on structurally bounded expansion classes.
  • domain assumption Algorithmic version of the Flipper-game characterization of monadically stable classes
    Used in Theorem 32 to obtain efficiently computable quasi-bounded-size bounded-shrubdepth decompositions, which underpin the results on monadically stable classes.
  • standard math Aggregate-query evaluation theorem for bounded-expansion classes
    Used in Lemma 26 to compute max-plus aggregate queries on bounded-expansion classes.
invented entities (2)
  • FO Cost-Value Decision independent evidence
    purpose: A general optimization problem where the value of a tuple is given by unary vertex weights and FO-definable correction terms.
    The paper proves FPT results for this problem on several graph classes and shows it captures Partial Vertex Cover Discovery.
  • Anchored weighted multicolored distance-r independence independent evidence
    purpose: A global packing problem formalizing the need to choose local candidates that are pairwise far apart.
    The paper proves this problem is FPT on the considered graph classes (Lemma 33, Lemma 31, Lemma 28).

how reviews work

0 comments
Cite this review

Pith. "Pith review of FO Value Discovery and Partial Vertex Cover Discovery." pith.science (2026). https://pith.science/paper/EVBOFN6N

@misc{pith2026260706446,
  author       = {Pith},
  title        = {Pith review of: FO Value Discovery and Partial Vertex Cover Discovery},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EVBOFN6N}},
  note         = {Machine review of arXiv:2607.06446}
}
abstract

We study solution discovery in the token-sliding model from a logical and cost-value optimization perspective. In solution discovery, we are given a graph, an initial placement of $k$ tokens, and a movement budget $b$. The task is to find a reachable target configuration satisfying a prescribed condition. Our results are inspired by \textsc{Partial Vertex Cover Discovery}, where the condition is that the~$k$ tokens cover at least $t$ edges of the input graph. This objective is not merely a sum of independent occupied vertex contributions: each selected vertex contributes its degree, but edges with both endpoints selected have to be subtracted once. To capture this phenomenon, we introduce \textsc{FO Value Discovery}, an optimization problem in which the value of a selected tuple is given by unary vertex weights together with first-order definable correction terms. We further generalize the setting to \textsc{FO Cost-Value Decision}, where vertices carry both costs and values, and the task is to decide whether there is a tuple whose first-order value expression reaches a prescribed value threshold while respecting a cost bound. Finally, we study the parameterized complexity of \textsc{Partial Vertex Cover Discovery} and \textsc{Vertex Cover Discovery}. As a consequence of the logical meta-theorems, we obtain fixed-parameter tractability of \textsc{Partial Vertex Cover Discovery} on several graph classes, including classes of locally bounded cliquewidth. We also show that \textsc{Partial Vertex Cover Discovery} is W[1]-hard parameterized by $k+b$ and fixed-parameter tractable on $d$-degenerate graphs parameterized by $k+d$. For \textsc{Vertex Cover Discovery}, we prove NP-hardness on planar graphs, W[1]-hardness parameterized by the clique cover number, even when a clique cover is supplied with the input, and W[1]-hardness with respect to parameter cutwidth.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    Mouawad, Stephanie Maaz, Naomi Nishimura, and Sebastian Siebertz

    1 Nicolas Bousquet, Amer E. Mouawad, Stephanie Maaz, Naomi Nishimura, and Sebastian Siebertz. On algorithmic meta-theorems for solution discovery: Tractability and barriers. CoRR, abs/2510.17344,

    work page arXiv

  2. [2]

    Mouawad, Stephanie Maaz, Naomi Nishimura, and Sebastian Siebertz

    URL:https://doi.org/10.48550/arXiv.2510.17344. 2 Samuel Braunfeld, Jaroslav Nesetril, Patrice Ossona de Mendez, and Sebastian Siebertz. Decomposition horizons and a characterization of stable hereditary classes of graphs.Eur. J. Comb., 129:104130,

    work page doi:10.48550/arxiv.2510.17344

  3. [3]

    3 Bruno Courcelle and Joost Engelfriet.Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 ofEncyclopedia of mathematics and its applications

    URL:https://doi.org/10.1016/j.ejc.2025.104130. 3 Bruno Courcelle and Joost Engelfriet.Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 ofEncyclopedia of mathematics and its applications. Cambridge University Press,

    work page doi:10.1016/j.ejc.2025.104130 2025

  4. [4]

    4 Bruno Courcelle, Johann A

    URL:https://doi.org/10.1017/CBO9780511977619. 4 Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width.Theory Comput. Syst., 33(2):125–150,

    work page doi:10.1017/cbo9780511977619

  5. [5]

    5 Marek Cygan, Fedor V

    URL:https://doi.org/10.1007/s002249910009. 5 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer,

    work page doi:10.1007/s002249910009

  6. [6]

    Fomin and Lukasz Kowalik and Daniel Lokshtanov and D

    URL:https://doi.org/10.1007/978-3-319-21275-3. 6 Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, and Morteza Zadimoghaddam. Minimizing movement. In Nikhil E. Gerhard, S. Maaz, P. Schott, S. Siebertz, and J. Wodtke 27 Bansal, Kirk Pruhs, and Clifford Stein, editors,Proceedings of the Eighteenth Annual...

    work page doi:10.1007/978-3-319-21275-3 2007

  7. [7]

    7 Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michal Pilipczuk, and Szymon Torunczyk

    URL: http://dl.acm.org/citation.cfm?id=1283383.1283411. 7 Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michal Pilipczuk, and Szymon Torunczyk. First-order model checking on monadically stable graph classes. In65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, pages 21–30. IEEE,

    work page arXiv 2024

  8. [8]

    [CSUU08] R

    URL:https://doi.org/10.1109/FOCS61266.2024.00012. 8 Jan Dreier, Jakub Gajarský, and Michal Pilipczuk. Efficient reversal of transductions of sparse graph classes. In Aditya Bhaskara and Artur Czumaj, editors,Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC 2026, pages 1180–1191. ACM,

    work page doi:10.1109/focs61266.2024.00012 2024

Show all 33 references
  1. [9]

    9 Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz

    URL: https://doi.org/10.1145/3798129.3800829. 9 Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz. First-order model checking on structurally sparse graph classes. In Barna Saha and Rocco A. Servedio, editors,Proceedings of the 55th Annual ACM Symposium on Theory of Computi...

    2023 doi

  2. [10]

    10 Michael R

    URL:https://doi.org/10.1145/3564246.3585186. 10 Michael R. Fellows, Mario Grobler, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Frances A. Rosamond, Daniel Schmand, and Sebastian Siebertz. On solution discovery via reconfiguration.J. Comput. Syst. Sci., 157:103747,

    doi

  3. [11]

    org/10.1016/j.jcss.2025.103747

    URL: https://doi. org/10.1016/j.jcss.2025.103747. 11 Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, and Szymon Torunczyk. First-order interpretations of bounded expansion classes.ACM Trans. Comput. Log., 21(...

    2025 doi

  4. [13]

    org/10.1145/3382093

    URL: https://doi. org/10.1145/3382093. 13 Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michal Pilipczuk, Woj- ciech Przybyszewski, Sebastian Siebertz, Marek Sokolowski, and Szymon Torunczyk. Flipper games for monadically stable graph classes. In Kousha Etess...

    2023 doi

  5. [14]

    14 Mario Grobler, Stephanie Maaz, Nicole Megow, Amer E

    URL:https://doi.org/10.4230/LIPIcs.ICALP.2023.128. 14 Mario Grobler, Stephanie Maaz, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Daniel Schmand, and Sebastian Siebertz. Solution discovery via reconfig- uration for problems in P. In Karl Bringmann, Martin Grohe...

    2023 doi

  6. [15]

    15 Mario Grobler, Stephanie Maaz, Amer E

    URL:https://doi.org/10.4230/LIPIcs.ICALP.2024.76. 15 Mario Grobler, Stephanie Maaz, Amer E. Mouawad, Naomi Nishimura, Vijayaragunathan Ramamoorthi, and Sebastian Siebertz. Kernelization complexity of solution discovery problems. In Julián Mestre and Anthony Wirth, editors,35th...

    2024 doi

  7. [16]

    URL:https://doi.org/10.4230/LIPIcs.ISAAC.2024.36

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL:https://doi.org/10.4230/LIPIcs.ISAAC.2024.36. 16 Martin Grohe and Stephan Kreutzer. Methods for algorithmic meta theorems. In Martin Grohe and Johann A. Makowsky, editors,Model Theoretic Methods in Finite Combinatorics - A...

    2024 doi

  8. [17]

    17 Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz

    URL:https://doi.org/10.1090/conm/558/11051. 17 Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs.J. ACM, 64(3):17:1–17:32,

    doi

  9. [18]

    28 FO Value and Partial Vertex Cover Discovery 18 Martin Grohe and Nicole Schweikardt

    URL:https://doi.org/10.1145/ 3051095. 28 FO Value and Partial Vertex Cover Discovery 18 Martin Grohe and Nicole Schweikardt. First-order query evaluation with cardinality conditions. In Jan Van den Bussche and Marcelo Arenas, editors,Proceedings of the 37th ACM SIGMOD- SIGACT-...

    2018

  10. [19]

    19 Martin Grohe and Nicole Schweikardt

    URL:https://doi.org/10.1145/3196959.3196970. 19 Martin Grohe and Nicole Schweikardt. A rank-preserving gaifman normal form,

    doi

  11. [20]

    20 Bart M

    URL: https://doi.org/10.48550/arXiv.2606.11993. 20 Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montec- chiani, and Kirill Simonov. Upward and orthogonal planarity are w[1]-hard parameter- ized by treewidth. In Michael A. Bekos and Markus C...

    2023 doi arXiv

  12. [21]

    21 Dietrich Kuske and Nicole Schweikardt

    URL: https: //doi.org/10.1007/978-3-031-49275-4_14. 21 Dietrich Kuske and Nicole Schweikardt. First-order logic with counting. In32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, pages1–12.IEEEComputer Society,

    2017 doi

  13. [22]

    22 Leonid Libkin.Elements of Finite Model Theory

    URL:https://doi.org/10.1109/LICS.2017.8005133. 22 Leonid Libkin.Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer,

    2017 doi

  14. [23]

    24 Moni Naor, Leonard J

    URL:https://doi.org/10.1145/2402.322385. 24 Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In36th Annual Symposium on Foundations of Computer Science, FOCS 1995, pages 182–191. IEEE Computer Society,

    1995 doi

  15. [24]

    1995.492475

    URL:https://doi.org/10.1109/SFCS. 1995.492475. 25 Jaroslav Nesetril and Patrice Ossona de Mendez. Grad and classes with bounded expansion i. decompositions.Eur. J. Comb., 29(3):760–776,

    1995 doi

  16. [25]

    ejc.2006.07.013

    URL:https://doi.org/10.1016/j. ejc.2006.07.013. 26 Jaroslav Nesetril and Patrice Ossona de Mendez.Sparsity - Graphs, Structures, and Algorithms, volume 28 ofAlgorithms and combinatorics. Springer,

    2006 doi

  17. [26]

    28 Sang-il Oum and Paul D

    URL:https: //doi.org/10.3390/a11040052. 28 Sang-il Oum and Paul D. Seymour. Approximating clique-width and branch-width.J. Comb. Theory B, 96(4):514–528,

    doi

  18. [27]

    29 Fahad Panolan and Hannane Yaghoubizade

    URL:https://doi.org/10.1016/j.jctb.2005.10.006. 29 Fahad Panolan and Hannane Yaghoubizade. Partial vertex cover on graphs of bounded degen- eracy. In Alexander S. Kulikov and Sofya Raskhodnikova, editors,17th International Computer Science Symposium in Russia, CSR 2022, volume...

    2005 doi

  19. [28]

    30Michael L

    URL:https://doi.org/10.1007/978-3-031-09574-0_18. 30Michael L. Pinedo.Scheduling: Theory, Algorithms, and Systems. Springer, 5 edition,

    doi

  20. [29]

    Solution discovery for vertex cover, independent set, dominating set, and feedback vertex set

    31 Rin Saito, Anouk Sommer, Tatsuhiro Suga, Takahiro Suzuki, and Yuma Tamura. Solution discovery for vertex cover, independent set, dominating set, and feedback vertex set. In Jakub Kozik and Alexander Wolff, editors,51st International Conference on Current Trends in Theory an...

    2026

  21. [30]

    32 Szymon Torunczyk

    URL: https://doi.org/10.1007/ 978-3-032-17801-5_32. 32 Szymon Torunczyk. Aggregate queries on sparse databases. In Dan Suciu, Yufei Tao, and Zhewei Wei, editors,Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, pages 427–443. ACM,

    2020

  22. [31]

    33 Steffen van Bergerem and Nicole Schweikardt

    URL: https: //doi.org/10.1145/3375395.3387660. 33 Steffen van Bergerem and Nicole Schweikardt. Learning concepts described by weight ag- gregation logic. In Christel Baier and Jean Goubault-Larrecq, editors,29th EACSL Annual Conference on Computer Science Logic, CSL 2021, volu...

    2021 doi

  23. [32]

    34 Steffen van Bergerem and Nicole Schweikardt

    URL:https://doi.org/10.4230/ LIPIcs.CSL.2021.10. 34 Steffen van Bergerem and Nicole Schweikardt. On the VC dimension of first-order logic with counting and weight aggregation. In Jörg Endrullis and Sylvain Schmitz, editors, 33rd EACSL Annual Conference on Computer Science Logi...

    2021

  24. [33]

    35 Hanno von Bergen, Larissa Fastenau, Enna Gerhard, Nicola Lorenz, Stephanie Maaz, Amer E

    URL: https://doi.org/10.4230/LIPIcs.CSL.2025.15. 35 Hanno von Bergen, Larissa Fastenau, Enna Gerhard, Nicola Lorenz, Stephanie Maaz, Amer E. Mouawad, Roman Rabinovich, Nicole Schirrmacher, Daniel Schmand, Sebastian Siebertz, and Mai Trinh. Separating feasibility and movement i...

    2025 doi arXiv

  25. [34]

    URL:https://doi.org/10.48550/arXiv.2604. 27802

    doi

Pith tools

Reviewed July 8, 2026 · model on record in the stance chip above.