Cover Image

A Tight Meta-theorem for LOCAL Certification of MSO$_2$ Properties within Bounded Treewidth Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cook, Linda, Kim, Eun Jung, Masařík, Tomáš
Format:	Preprint
Published:	2025
Subjects:	Distributed, Parallel, and Cluster Computing Discrete Mathematics Data Structures and Algorithms 68R10 F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Local certification of forbidden subgraphs
by: Bousquet, Nicolas, et al.
Published: (2024)

GenTT: Generate Vectorized Codes for General Tensor Permutation
by: Chen, Yaojian, et al.
Published: (2025)

Fast algorithms for Vizing's theorem on bounded degree graphs
by: Bernshteyn, Anton, et al.
Published: (2023)

A Tight Lower Bound for 3-Coloring Grids in the Online-LOCAL Model
by: Chang, Yi-Jun, et al.
Published: (2023)

Parallelizing the Approximate Minimum Degree Ordering Algorithm: Strategies and Evaluation
by: Chang, Yen-Hsiang, et al.
Published: (2025)

Renaming in distributed certification
by: Bousquet, Nicolas, et al.
Published: (2024)

A subquadratic certification scheme for P5-free graphs
by: Bousquet, Nicolas, et al.
Published: (2024)

Complexity landscape for local certification
by: Bousquet, Nicolas, et al.
Published: (2025)

Local Ratio based Real-time Job Offloading and Resource Allocation in Mobile Edge Computing
by: Gao, Chuanchao, et al.
Published: (2025)

Computing in Anonymous Dynamic Networks Is Linear
by: Di Luna, Giuseppe A., et al.
Published: (2022)

Simpler and More General Distributed Coloring Based on Simple List Defective Coloring Algorithms
by: Fuchs, Marc, et al.
Published: (2024)

Efficient Parallel $(Δ+1)$-Edge-Coloring
by: Elkin, Michael, et al.
Published: (2026)

Tight Bounds for Constant-Round Domination on Graphs of High Girth and Low Expansion
by: Lenzen, Christoph, et al.
Published: (2024)

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

Reductions in local certification
by: Esperet, Louis, et al.
Published: (2025)

Scheduled Jacobian Chaining
by: Märtens, Simon, et al.
Published: (2025)

A Randomised Approach to Distributed Sorting
by: Olesker-Taylor, Sam
Published: (2025)

Tight Bounds on the Message Complexity of Distributed Tree Verification
by: Kutten, Shay, et al.
Published: (2024)

Decentralized Distributed Graph Coloring: Cluster Graphs
by: Flin, Maxime, et al.
Published: (2024)

Model-Agnostic Approximation of Constrained Forest Problems
by: Coupette, Corinna, et al.
Published: (2024)

Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs
by: Faour, Salwa, et al.
Published: (2025)

Reducing Matroid Optimization to Basis Search
by: Streit, Robert, et al.
Published: (2024)

Low-Distortion Clustering in Bounded Growth Graphs
by: Chang, Yi-Jun, et al.
Published: (2024)

Deterministic Fault-Tolerant Local Load Balancing and its Applications against Adaptive Adversaries
by: Kowalski, Dariusz R., et al.
Published: (2025)

High-Quality Multi-Constraint Hypergraph Partitioning via Greedy Rebalancing
by: Maas, Nikolai
Published: (2026)

Low-Depth Spatial Tree Algorithms
by: Baumann, Yves, et al.
Published: (2024)

RadiK: Scalable and Optimized GPU-Parallel Radix Top-K Selection
by: Li, Yifei, et al.
Published: (2025)

Memory Bounds for Concurrent Bounded Queues
by: Aksenov, Vitaly, et al.
Published: (2021)

HiPerMotif: Novel Parallel Subgraph Isomorphism in Large-Scale Property Graphs
by: Dindoost, Mohammad, et al.
Published: (2025)

Orientation does not help with 3-coloring a grid in online-LOCAL
by: Boudier, Thomas, et al.
Published: (2025)

Dynamic Approximate Maximum Matching in the Distributed Vertex Partition Model
by: Robinson, Peter, et al.
Published: (2025)

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
by: Bonnet, Édouard, et al.
Published: (2023)

Bounded Memory in Distributed Networks
by: Basat, Ran Ben, et al.
Published: (2025)

Narrowing the LOCAL$\unicode{x2013}$CONGEST Gaps in Sparse Networks via Expander Decompositions
by: Chang, Yi-Jun, et al.
Published: (2022)

Meta-Theorems for Cuttable Distributed Problems
by: Bonamy, Marthe, et al.
Published: (2026)

Improved Approximation Bounds for Minimum Weight Cycle in the CONGEST Model
by: Manoharan, Vignesh, et al.
Published: (2023)

Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model
by: Manoharan, Vignesh, et al.
Published: (2022)

Deterministic Lower Bounds for $k$-Edge Connectivity in the Distributed Sketching Model
by: Robinson, Peter, et al.
Published: (2025)

Multi-Agent Online Graph Exploration on Cycles and Tadpole Graphs
by: Akker, Erik van den, et al.
Published: (2024)

Amnesiac Flooding: Easy to break, hard to escape
by: Austin, Henry, et al.
Published: (2025)