Pith. sign in

REVIEW 5 minor 1 cited by

Optimal local certification on graphs of bounded pathwidth

T0 review · 0 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read The paper proves that any graph property expressible in MSO2 logic—planarity, Hamiltonicity, k-colorability, and more—can be locally certified with O(log n)-bit vertex labels on graphs of bounded pathwidth, and that this label size is…

desk verdict The paper delivers a genuinely new optimal O(log n) certification meta-theorem for bounded-pathwidth graphs and resolves the forest-minor-free open question; the hardest congestion proof holds up under scrutiny. read the letter →

arxiv 2502.00676 v1 pith:FSGO6NUF submitted 2025-02-02 cs.DC cs.DS

Dan Alden Baterisna , Yi-Jun Chang This is my paper · ORCID
classification cs.DCcs.DS MSC 68W1505C8305C85
keywords prooflabelingschemeslocalcertificationpathwidthmonadicsecond-orderlogicCourcelle'stheoremgraphminorsF-minor-freegraphsdistributedverification
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 establishes a meta-theorem for local certification: for any fixed integer $k$ and any graph property $\phi$ expressible in MSO2 logic, the property "the graph satisfies $\phi$ and has pathwidth at most $k$" can be certified by a proof labeling scheme with $O(\log n)$-bit vertex labels. This improves the previous $O(\log^2 n)$-bit result for bounded treewidth and matches the $\Omega(\log n)$ lower bound that already applies to the simplest such classes. As a corollary, combining the result with the Excluding Forest Theorem of Robertson and Seymour shows that graphs excluding any fixed forest $F$ as a minor can be certified with $O(\log n)$-bit labels, answering an open question. The proof rests on a new decomposition of bounded-pathwidth graphs into $O(1)$ lanes whose completion embeds into the original graph with $O(1)$ congestion.

What carries the argument

The load-bearing objects are $k$-lane recursive graphs: $k$-lane graphs (graphs with in- and out-terminals assigned to lanes) closed under two merge operations—Bridge-merge, which joins two graphs on disjoint lane sets by adding one edge between out-terminals, and Tree-merge, which glues child in-terminals to the parent's out-terminals along a tree. The paper proves such graphs have hierarchical decompositions of depth at most $2k$ (Observation 5.5), and that the homomorphism class of an MSO2 property is computable over these merges (Proposition 6.1). The bridge from arbitrary bounded-pathwidth graphs to these recursive graphs is Proposition 4.6, which constructs a lane partition of a width-$k$ interval representation with congestion at most $h(k)$ for the completion.

What would settle it

Construct a width-3 interval representation where a long $v_{st}$-$v_{ed}$ path interleaves many small connected components between consecutive vertices of $S$, and count how many crossing paths in Case 2.2 of Proposition 4.6 use a single edge of that path; if the count grows with the number of components, the claimed $O(1)$ congestion bound is false.

Watch

Extended reading notes

Core claim

The central discovery is that bounded-pathwidth graphs, viewed through their interval representations, admit a lane partition into $O(f(k))$ lanes whose "completion"—adding edges to link consecutive intervals in each lane and to connect lane starts—can be embedded back into the original graph with $O(1)$ congestion per original edge, for constant $k$. The completed graph is a $k$-lane recursive graph built by Bridge-merge and Tree-merge operations, and any such graph can be generated by a hierarchical decomposition of depth at most $2k$. Because the decomposition has constant depth, each original edge belongs to only $O(1)$ nodes of the decomposition, so the dynamic-programming homomorphism classes from Courcelle's theorem can be certified edge-by-edge at constant congestion overhead, yielding $O(\log n)$-bit edge labels and, after the standard edge-to-vertex transformation, $O(\log n)$-bit vertex labels.

Load-bearing premise

The entire construction rests on the claim that any width-$k$ interval representation of a connected graph can be partitioned into $O(1)$ lanes so that the completed graph embeds into the original graph with $O(1)$ congestion, independent of the number of connected components.

Editorial extensions

If this is right

  • For every fixed $k$ and every MSO2 property $\phi$, the property "$\phi$ and pathwidth at most $k$" is certifiable with $O(\log n)$-bit labels, and this is optimal because the same lower bound holds for paths versus cycles.
  • Any fixed forest $F$ yields an $O(\log n)$-bit proof labeling scheme for $F$-minor-free graphs, thereby resolving the open question about certifying tree-minor-free and forest-minor-free graph classes.
  • The certification works by verifying an execution of Courcelle-style dynamic programming, so it applies uniformly to a broad list of properties, including planarity, Hamiltonicity, $k$-colorability, perfect matching, and having a vertex cover of given size.
  • The construction produces $O(\log n)$-bit edge labels in bounded-degeneracy graphs, and the standard transformation to vertex labels preserves the $O(\log n)$ bound because bounded-pathwidth graphs have bounded degeneracy.

Reading between the lines

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

  • If the lane-based ideas could be adapted to handle the disconnected bags of a tree decomposition, the bounded-treewidth analogue might drop from $O(\log^2 n)$ to $O(\log n)$; by the Excluding Grid Theorem that would also imply optimal certification of $H$-minor-free graphs for every planar $H$.
  • A concrete stress-test family consisting of many small connected components interleaved along the $v_{st}$-$v_{ed}$ path would reveal whether the $O(1)$ congestion bound in Proposition 4.6 is truly independent of the number of components, since that independence is the load-bearing part of the argument.
  • The $k$-lane recursive graph toolbox may be reusable beyond certification—for example as a structural primitive for distributed approximation, routing, or decomposition algorithms on pathwidth-bounded networks.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper presents a proof labeling scheme (PLS) for every MSO2 graph property on graphs of pathwidth at most k, using O(log n)-bit vertex labels, thereby improving the O(log^2 n)-bit scheme of Fraigniaud et al. for bounded treewidth. The approach is based on a new structural decomposition: every bounded-pathwidth graph admits an interval representation whose intervals can be partitioned into O(1) lanes, and the resulting "completion" (connecting each lane into a path and connecting lane starts) embeds into the original graph with O(1) congestion. The completed graph is shown to be a k-lane recursive graph with a bounded-depth hierarchical decomposition, which allows certifying the execution of Courcelle-style dynamic programming over homomorphism classes with O(log n)-bit labels. As a corollary, using the Robertson-Seymour Excluding Forest Theorem, the class of F-minor-free graphs for every fixed forest F is certified with O(log n)-bit labels, answering an open question of Bousquet, Feuilloley, and Pierron.

Significance. If correct, the result is a significant advance in local certification: it gives an optimal O(log n)-bit meta-theorem for all MSO2 properties on bounded-pathwidth graphs, and it resolves a concrete open question on forest minor-free classes. The paper is self-contained relative to standard tools (Courcelle's theorem, the Excluding Forest Theorem, and the KKP lower bound) and does not introduce fitted parameters. The constants f(k), g(k), h(k) are explicit, and the congestion analysis gives a concrete O(1) bound depending only on k. The construction of k-lane recursive graphs and the certification of their homomorphism classes are original and appear to be mechanistically sound. The main risk is the subtle congestion accounting in Proposition 4.6, which is terse; however, I checked the two places where a component-count factor could hide and found that the additive argument is consistent. The paper is not machine-checked, but the proof structure is detailed enough for a careful reader to verify. Overall, this is a strong and publishable contribution.

minor comments (5)
  1. [§4.2, Observation 4.9] The proof contains a false equality: it reads "max_{v in S} R_v = R_{v_ed} = min_{v in V} L_v", but the second equality should be "= max_{v in V} R_v". The observation itself is correct, but this typo should be fixed.
  2. [§5.4, Proposition 5.6 Case 1] In the description of the E-node created for a V-insert operation, the equation "tau_in^i(G*) = v, and tau_in^i(G*) = tau_i" repeats the same symbol; the second occurrence should be "tau_out^i(G*)". Please correct this.
  3. [§4.2, Case 2.2] The claim that for each triple (i,j,ell) each edge of P participates at most once in the middle portions of the crossing-edge paths is correct, but it is not fully justified in the text. A short explanation using the order of the attachment vertices v*_C along P and the pairwise disjointness of the intervals {I_C : C in C_i} from Lemma 4.10 would make the congestion bound easier for readers to verify.
  4. [§6.2, Lemma 6.5] In the B-node paragraph, "in-teriminals" and "out-teriminals" are typos for "in-terminals" and "out-terminals". Elsewhere in the same lemma, the phrase "the right in-terminal" should probably be "the corresponding in-terminal".
  5. [§1.4] The statement that (pathwidth <= k) is an MSO2 graph property would benefit from a citation, e.g., to the standard Courcelle/Arnborg-Lagergren-Seese literature, since it is load-bearing for the self-certification of bounded pathwidth.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained and rests on external theorems, not on its own conclusion.

full rationale

The derivation chain of Theorem 1 is constructive and does not reduce to its inputs. The proof combines: (1) the standard interval-representation view of path decompositions; (2) Proposition 4.6, which is an independent geometric construction with explicit recurrences f(k), g(k), h(k) and no fitted quantity; (3) Proposition 5.2, an equivalence between lanewidth and completions of k-lane partitions, proved by explicit translations in both directions; (4) Proposition 6.1, which transfers Courcelle's homomorphism-class machinery (Proposition 2.4, [BPT92; Cou90]) to k-lane recursive graphs via a 3k-terminal encoding; and (5) Lemma 6.5/Proposition 6.2, which certifies the recursive construction with O(log n)-bit labels whose size depends only on the constants f(k+1), h(k+1) and Observation 5.5's bounded depth. The only self-citations ([Cha23], [CS22]) are related-work references and are not load-bearing. The lower bound is the external KKP10 path-vs-cycle separation, and Corollary 1.2 uses the external Excluding Forest Theorem [RS83]. No parameter is fitted to data, no prediction is a renamed input, and no uniqueness or ansatz is imported from prior work of the same authors. The typographical slip in Observation 4.9 (writing min L_v where max R_v is intended) is a correctness-risk typo, not a circularity. I find no circular step.

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

The paper is a pure mathematics and theory result. It introduces no empirical entities and fits no parameters. It relies on standard theorems from graph theory and distributed computing, listed above.

assumptions (5)
  • standard math Courcelle's theorem and Proposition 2.4: any MSO2 property is decidable in linear time on bounded-treewidth graphs via finite homomorphism classes over k-terminal recursive graphs.
    Used to define homomorphism classes h* for k-lane recursive graphs in Section 6.1.
  • standard math Robertson-Seymour Excluding Forest Theorem: for every forest F, there exists k such that all F-minor-free graphs have pathwidth at most k.
    Used in Corollary 1.2 to derive F-minor-free certification.
  • standard math Lower bound from KKP10: any proof labeling scheme that accepts paths and rejects cycles requires Omega(log n)-bit labels.
    Used to prove optimality of O(log n) in Section 1.4.
  • standard math Interval graphs are perfect: any interval collection of width k can be partitioned into k sets of pairwise disjoint intervals.
    Used in Observation 4.3 and Lemma 4.10.
  • standard math Proposition 2.1 from FFM+23: a proof labeling scheme on a d-degenerate graph using f(n)-bit edge labels can be transformed into a scheme using O(d * f(n))-bit vertex labels.
    Used in Theorem 1 to convert edge labels to vertex labels.
invented entities (1)
  • k-lane recursive graphs and the associated merge operations (Bridge-merge, Parent-merge, Tree-merge)
    purpose: Provide a bounded-depth hierarchical decomposition of bounded-pathwidth graphs that permits O(1) congestion simulation of dynamic programming over homomorphism classes.
    Mathematical construction defined in Sections 5.2-5.4. No empirical claims; used purely as a proof device, so no independent falsifiable handle exists.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal local certification on graphs of bounded pathwidth." pith.science (2026). https://pith.science/paper/FSGO6NUF

@misc{pith2026250200676,
  author       = {Pith},
  title        = {Pith review of: Optimal local certification on graphs of bounded pathwidth},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FSGO6NUF}},
  note         = {Machine review of arXiv:2502.00676}
}
abstract

We present proof labeling schemes for graphs with bounded pathwidth that can decide any graph property expressible in monadic second-order (MSO) logic using $O(\log n)$-bit vertex labels. Examples of such properties include planarity, Hamiltonicity, $k$-colorability, $H$-minor-freeness, admitting a perfect matching, and having a vertex cover of a given size. Our proof labeling schemes improve upon a recent result by Fraigniaud, Montealegre, Rapaport, and Todinca (Algorithmica 2024), which achieved the same result for graphs of bounded treewidth but required $O(\log^2 n)$-bit labels. Our improved label size $O(\log n)$ is optimal, as it is well-known that any proof labeling scheme that accepts paths and rejects cycles requires labels of size $\Omega(\log n)$. Our result implies that graphs with pathwidth at most $k$ can be certified using $O(\log n)$-bit labels for any fixed constant $k$. Applying the Excluding Forest Theorem of Robertson and Seymour, we deduce that the class of $F$-minor-free graphs can be certified with $O(\log n)$-bit labels for any fixed forest $F$, thereby providing an affirmative answer to an open question posed by Bousquet, Feuilloley, and Pierron (Journal of Parallel and Distributed Computing 2024).

Figures

Figures reproduced from arXiv: 2502.00676 by the authors.

Figure 1
Figure 1. Path decomposition and interval representation of a [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Combining two 3-terminal graphs into a 3-terminal graph. See [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Weak completion and completion. Definition 4.5. Let G = (V, E) and G′ = (V, E′ ) be two graphs on the same vertex set V with E ⊆ E′ . An embedding E = {Pe | e ∈ E′ \ E} of G′ into G is an assignment of a u-v path Pe in G to each edge e = {u, v} ∈ E′ \ E. The congestion of an embedding E is the maximum number of paths in E that an edge belongs to. We explain the motivation behind the above definition, as follows. Sup… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Graph terminology in Section 4.2. Observation 4.7. For all 1 ≤ i < |S|, Rsi < Rsi+1. Proof. If Rsi ≥ Rsi+1, then Ru ≤ Rsi for all vertices u in P after si such that Iu ∩Isi ̸= ∅, implying that Rsi = Rved , so the construction of S stops at vi , contradicting the existe…
Figure 5
Figure 5. Figure 5: Case 1 in the proof of Proposition 4.6. Case 2. In the second case, we consider the cost of transforming the lane S C∈Cj i P ℓ C into a path for all i ∈ [k − 1], j ∈ {1, 2}, and ℓ ∈ [f(k − 1)]. We further divide the analysis into two subcases. Case 2.1. We consider the…
Figure 6
Figure 6. Figure 6: Case 2.2 in the proof of Proposition 4.6. Next, we consider the middle portion (v ∗ C , . . . , v∗ C′) of the path Pe. For each (i, j, ℓ), each edge in P participates at most once in the transformation of the lane S C∈Cj i P ℓ C into a path. Therefore, the overall cost…
Figure 7
Figure 7. Figure 7: A bounded-lanewidth graph. In Section 5.1, we give an alternative definition of lanewidth using the completion of a k-lane partition. In Section 5.2, we introduce the notion of k-lane recursive graphs. In Sections 5.2 and 5.3, we consider a specific way to construct k-…
Figure 8
Figure 8. Figure 8: Bridge-merge and Parent-merge Parent-merge. Suppose T (G1) ⊆ T (G2). We define Parent-merge(G1, G2) as the k-lane graph G = (V, E) resulting from identifying τ in i (G1) with τ out i (G2) for each i ∈ T (G1). We set T (G) = T (G2). The in-terminals and the out-terminal…
Figure 9
Figure 9. Figure 9: Tree-merge 1. Start from the tree T. 2. While there still exists an edge e = {G1, G2} in the tree, where G1 is a child of G2, contract the edge e = (G1, G2) into Parent-merge(G1, G2). Observe that Parent-merge is associative in that the ordering of the edges in the whi…
Figure 10
Figure 10. Figure 10: Constructing a bounded-lanewidth graph as a [PITH_FULL_IMAGE:figures/full_fig_p023_10.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Complexity landscape for local certification

    cs.DC 2025-05 conditional novelty 8.0 of 10

    On anonymous paths local certification has a gap between O(1) and Θ(log log n), and a natural property with optimal Θ(log log n) certificates exists; on cycles the gap is between O(1) and Θ(log n).

Reference graph

Works this paper leans on

21 extracted references · 18 canonical work pages · cited by 1 Pith paper

  1. [1]

    Memory-efficient self stabilizing protocols for general networks

    [AKY91] Yehuda Afek, Shay Kutten, and Moti Yung. Memory-efficient self stabilizing protocols for general networks. InDistributed Algorithms: 4th International Workshop (WDAG 1990), pages 15–28. Springer,

    work page 1990

  2. [8]

    doi: 10.4230/LIPIcs.DISC.2020.20

    isbn: 978-3-95977-168-9. doi: 10.4230/LIPIcs.DISC.2020.20. url: https://drops. dagstuhl.de/opus/volltexte/2020/13098. [EL22] Louis Esperet and Benjamin Lévêque. Local certification of graphs on surfaces. Theo- retical Computer Science, 909:68–75, 2022.issn: 0304-3975. [Ele22] Gábor Elek. Planarity can be verified by an approximate proof labeling scheme in...

    work page doi:10.4230/lipics.disc.2020.20 2020

  3. [9]

    Testability and Local Certification of Monotone Prop- erties in Minor-Closed Classes

    [EN22] Louis Esperet and Sergey Norin. Testability and Local Certification of Monotone Prop- erties in Minor-Closed Classes. In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Pro- gramming (ICALP 2022), volume 229 ofLeibniz International Proceedings in Informat- ics (LIPIcs), ...

    work page 2022

  4. [10]

    30 [FBP22] Laurent Feuilloley, Nicolas Bousquet, and Théo Pierron

    isbn: 978-3-95977-235-8. 30 [FBP22] Laurent Feuilloley, Nicolas Bousquet, and Théo Pierron. What can be certified com- pactly? compact local certification of mso properties in tree-like graphs. InProceed- ings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC), pages 131–140,

    work page 2022

  5. [11]

    Bibliography of distributed approximation beyond bounded degree

    [Feu20] Laurent Feuilloley. Bibliography of distributed approximation beyond bounded degree. arXiv preprint arXiv:2001.08510,

    arXiv 2001

  6. [12]

    Introduction to local certification

    [Feu21] Laurent Feuilloley. Introduction to local certification. Discrete Mathematics & Theo- retical Computer Science, vol. 23, no. 3, September 2021.doi: 10.46298/dmtcs.6280. url: https://dmtcs.episciences.org/8479. [FFM+21] Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. Compact distributed certif...

    doi:10.46298/dmtcs.6280 2021

  7. [13]

    Fomin, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Tod- inca

    [FFM+24] Fedor V. Fomin, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Tod- inca. Distributed Model Checking on Graphs of Bounded Treedepth. In Dan Alis- tarh, editor, 38th International Symposium on Distributed Computing (DISC 2024), volume 319 ofLeibniz International Proceedings in Informatics (LIPIcs), 25:1–25:20, Dagstuhl, Germany. Sch...

    work page 2024

  8. [17]

    4086 / toc

    doi: 10 . 4086 / toc . 2016 . v012a019. url: https://theoryofcomputing.org/articles/v012a019. [HIZ16a] Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Low-congestion shortcuts without embedding. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), pages 451–460,

    work page 2016

Show all 21 references
  1. [18]

    Minor excluded network families admit fast distributed algorithms

    [HLZ18] Bernhard Haeupler, Jason Li, and Goran Zuzic. Minor excluded network families admit fast distributed algorithms. InProceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 465–474,

    2018

  2. [25]

    dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.25

    url: https : / / drops . dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.25. [FMR+24] Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. A meta- theorem for distributed certification.Algorithmica, 86(2):585–612,

    2024 doi

  3. [1992]

    Efficient distributed decomposition and routing algorithms in minor- free networks and their applications

    [Cha23] Yi-Jun Chang. Efficient distributed decomposition and routing algorithms in minor- free networks and their applications. InProceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC), pages 55–66,

    2023

  4. [2004]

    1016/j.jctb.2004.08.001

    doi: https://doi.org/10. 1016/j.jctb.2004.08.001. Special Issue Dedicated to Professor W.T. Tutte. [RS83] Neil Robertson and Paul D Seymour. Graph minors. I. excluding a forest. Journal of Combinatorial Theory, Series B, 35(1):39–61, 1983.issn: 0095-8956. [RS86] Neil Robertson...

    2004

  5. [2005]

    1109 / SFCS.2005.14

    doi: 10 . 1109 / SFCS.2005.14. [EG20] Yuval Emek and Yuval Gil. Twenty-Two New Approximate Proof Labeling Schemes. In Hagit Attiya, editor,34th International Symposium on Distributed Computing (DISC 2020), volume 179 ofLeibniz International Proceedings in Informatics (LIPIcs),...

    2005

  6. [2007]

    Interactive distributed proofs

    [KOS18] Gillat Kol, Rotem Oshman, and Raghuvansh R Saxena. Interactive distributed proofs. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 255–264,

    2018

  7. [2016]

    Low-congestion shortcuts for graphs exclud- ing dense minors

    [GH21] Mohsen Ghaffari and Bernhard Haeupler. Low-congestion shortcuts for graphs exclud- ing dense minors. InProceedings of the 2021 ACM Symposium on Principles of Dis- tributed Computing (PODC), pages 213–221,

    2021

  8. [2018]

    Fully polynomial-time distributed computation in low-treewidth graphs

    [IKN+22] Taisuke Izumi, Naoki Kitamura, Takamasa Naruse, and Gregory Schwartzman. Fully polynomial-time distributed computation in low-treewidth graphs. InProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 11–22, New York, NY, US...

    2022

  9. [2019]

    Distributed algorithms for planar networks I: planar embedding

    [GH16a] Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks I: planar embedding. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), pages 29–38,

    2016

  10. [2020]

    [CS22] Yi-Jun Chang and Hsin-Hao Su

    Special issue on Structural Informa- tion and Communication Complexit. [CS22] Yi-Jun Chang and Hsin-Hao Su. Narrowing the LOCAL–CONGEST gaps in sparse networks via expander decompositions. InProceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC), p...

    2022

  11. [2022]

    Downey and Michael R

    [DF16] Rodney G. Downey and Michael R. Fellows. Fundamentals of Parametrized Complexity. Springer London, London, 2016.isbn: 978-1-4471-7164-5. doi: https://doi.org/10. 1007/978-1-4471-5559-1. [DHK05] E.D. Demaine, M.T. Hajiaghayi, and K. Kawarabayashi. Algorithmic graph minor...

    2016

  12. [2023]

    The monadic second-order logic of graphs

    [Cou90] Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Information and Computation, 85(1):12–75, 1990.issn: 0890-5401. [CPP20] Keren Censor-Hillel, Ami Paz, and Mor Perry. Approximate proof-labeling schemes. Theoretical Comput...

    1990

  13. [2024]

    NC-algorithms for graphs with small treewidth

    29 [Bod89] Hans L Bodlaender. NC-algorithms for graphs with small treewidth. In proceedings of the 14th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 1988), pages 1–10. Springer,

    1988

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.