Cover Image

A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bergougnoux, Benjamin, Chekan, Vera, Stamoulis, Giannos
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Logic in Computer Science 68Q27, 05C85 F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
by: Golovach, Petr A., et al.
Published: (2022)

Steiner Tree Parameterized by Multiway Cut and Even Less
by: Jansen, Bart M. P., et al.
Published: (2024)

Mim-Width is paraNP-complete
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Tight Bounds for some W[1]-hard Problems Parameterized by Multi-clique-width
by: Bergougnoux, Benjamin, et al.
Published: (2026)

Parameterizing the quantification of CMSO: model checking on minor-closed graph classes
by: Sau, Ignasi, et al.
Published: (2024)

TreeWidzard: An Engine for Width-Based Dynamic Programming and Automated Theorem Proving
by: Oliveria, Mateus de Oliveira, et al.
Published: (2026)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

How quickly can you pack short paths? Engineering a search-tree algorithm for disjoint s-t paths of bounded length
by: Huber, Michael Kiran
Published: (2024)

Algorithms for Minimum Membership Dominating Set Problem
by: Reddy, Sangam Balchandar, et al.
Published: (2024)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
by: Jansen, Klaus, et al.
Published: (2024)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
by: Morse, Gregory, et al.
Published: (2026)

Odd Cycle Transversal on $P_5$-free Graphs in Polynomial Time
by: Agrawal, Akanksha, et al.
Published: (2024)

Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
by: Alpay, Faruk, et al.
Published: (2026)

Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
by: Komusiewicz, Christian, et al.
Published: (2023)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

Fast FPT Algorithms for Grundy Number on Dense Graphs
by: Nezhad, Sina Ghasemi, et al.
Published: (2024)

Finding irrelevant vertices in linear time on bounded-genus graphs
by: Golovach, Petr A., et al.
Published: (2019)

Faster parameterized algorithms for modification problems to minor-closed classes
by: Morelle, Laure, et al.
Published: (2022)

Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
by: Bojikian, Narek, et al.
Published: (2025)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
by: Philip, Geevarghese, et al.
Published: (2026)

Group Order Logic
by: Dahan, Anatole
Published: (2025)

ARRIVAL: Recursive Framework & $\ell_1$-Contraction
by: Haslebacher, Sebastian
Published: (2025)

State Canonization and Early Pruning in Width-Based Automated Theorem Proving
by: Oliveira, Mateus de Oliveira, et al.
Published: (2026)

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
by: Levet, Michael, et al.
Published: (2023)

Exact Algorithms for MaxCut on Split Graphs
by: Lalovic, Marko
Published: (2024)

Overlapping Biclustering
by: Bentert, Matthias, et al.
Published: (2025)

Simple minimally unsatisfiable subsets of 2-CNFs
by: Kullmann, Oliver, et al.
Published: (2026)

Tight Bounds for some Classical Problems Parameterized by Cutwidth
by: Bojikian, Narek, et al.
Published: (2025)

Competitive Query Minimization for Stable Matching with One-Sided Uncertainty
by: Bampis, Evripidis, et al.
Published: (2024)

The Bottom-Left Algorithm for the Strip Packing Problem
by: Hougardy, Stefan, et al.
Published: (2024)

Prediction-Augmented Mechanism Design for Weighted Facility Location
by: Shi, Yangguang, et al.
Published: (2025)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

Extending Exact Integrality Gap Computations for the Metric TSP
by: Cook, William, et al.
Published: (2026)

On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
by: Heimann, Sophia, et al.
Published: (2026)

A New Temporal Interpretation of Cluster Editing
by: Bocci, Cristiano, et al.
Published: (2022)

Decline and Fall of the ICALP 2008 Modular Decomposition algorithm
by: Atherton, William, et al.
Published: (2024)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
by: Grochow, Joshua A., et al.
Published: (2025)

Fully Dynamic Maintenance of Loop Nesting Forests in Reducible Flow Graphs
by: Morse, Gregory, et al.
Published: (2026)

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
by: Heimann, Sophia, et al.
Published: (2025)