Cover Image

Weighted Treedepth is NP-complete on Graphs of Bounded Degree

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dirks, Jona, Schirrmacher, Nicole, Siebertz, Sebastian, Vigny, Alexandre
Format:	Preprint
Published:	2025
Subjects:	Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Elimination Distance to Dominated Clusters
by: Schirrmacher, Nicole, et al.
Published: (2025)

Token Sliding Reconfiguration on DAGs
by: Dirks, Jona, et al.
Published: (2025)

Lower bounds for dominating set reconfiguration on sparse (directed) graphs
by: Dirks, Jona, et al.
Published: (2025)

Elimination distance to bounded degree on planar graphs
by: Lindermayr, Alexander, et al.
Published: (2020)

Advances in Algorithmic Meta Theorems
by: Siebertz, Sebastian, et al.
Published: (2024)

Broadcast Graph Is NP-complete
by: Xu, Jinghan, et al.
Published: (2024)

Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees
by: Gerke, Stefanie, et al.
Published: (2024)

On the generalized coloring numbers
by: Siebertz, Sebastian
Published: (2025)

Computing Treedepth Obstructions
by: Kühn, Kolja
Published: (2025)

Existential Positive Transductions of Sparse Graphs
by: Mählmann, Nikolas, et al.
Published: (2026)

A Note on Constructive Canonical Splitter Strategies in Nowhere Dense Graph Classes
by: Fuchser, Janne, et al.
Published: (2025)

String Graph Obstacles of High Girth and of Bounded Degree
by: Chudnovsky, Maria, et al.
Published: (2025)

Large Induced Subgraphs of Bounded Degree in Outerplanar and Planar Graphs
by: D'Elia, Marco, et al.
Published: (2024)

The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
by: Dreier, Jan, et al.
Published: (2026)

Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
by: von Bergen, Hanno, et al.
Published: (2026)

Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete
by: la Tour, Max Dupré, et al.
Published: (2025)

Property Testing in Bounded Degree Hypergraphs
by: Aaronson, Hugo, et al.
Published: (2025)

Why Districting Becomes NP-hard
by: Jost, Niklas, et al.
Published: (2025)

Lower Bounds for Maximum Weighted Cut
by: Gutin, Gregory, et al.
Published: (2021)

Determining the Outerthickness of Graphs Is NP-Hard
by: Lee, Pin-Hsian, et al.
Published: (2026)

Weighted Group Search on the Disk & Improved Lower Bounds for Priority Evacuation
by: Georgiou, Konstantinos, et al.
Published: (2024)

Minimum Spanning Trees with Bounded Degrees of Vertices in a Specified Stable Set
by: Brause, Christoph, et al.
Published: (2022)

Pushing Cops and Robber on Graphs of Maximum Degree 4
by: Gahlawat, Harmender
Published: (2025)

A Weight Function Lemma Heuristic for Graph Pebbling
by: Bridi, G. A., et al.
Published: (2025)

Bounds on Path Energy of Graphs
by: Narke, Amol P., et al.
Published: (2022)

Slant/Gokigen Naname is NP-complete, and Some Variations are in P
by: Lynch, Jayson, et al.
Published: (2025)

On Euler Paths and the Maximum Degree Growth of Iterated Higher Order Line Graphs
by: Sanghi, Aryan, et al.
Published: (2026)

Lower Bounds for Induced-Universal Graphs
by: Gavoille, Cyril, et al.
Published: (2025)

Supports for Outerplanar and Bounded Treewidth Graphs
by: Raman, Rajiv, et al.
Published: (2025)

Bounds on the Complete Forcing Number of Graphs
by: Ebrahimi, Javad B., et al.
Published: (2024)

p-complete square-free Word-representation of Word-representable Graphs
by: Das, Biswajit, et al.
Published: (2025)

A Survey of Cameron-Liebler Sets and Low Degree Boolean Functions in Grassmann Graphs
by: Ihringer, Ferdinand
Published: (2024)

Conflict-Free Coloring: Graphs of Bounded Clique Width and Intersection Graphs
by: Bhyravarapu, Sriram, et al.
Published: (2021)

On 1-Planar Graphs with Bounded Cop-Number
by: Bose, Prosenjit, et al.
Published: (2024)

Decomposition horizons and a characterization of stable hereditary classes of graphs
by: Braunfeld, Samuel, et al.
Published: (2022)

On first-order transductions of classes of graphs
by: Braunfeld, Samuel, et al.
Published: (2022)

Twin-width and permutations
by: Bonnet, Édouard, et al.
Published: (2021)

The formula for the completion time of project networks
by: Castejón-Limas, Manuel, et al.
Published: (2024)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
by: Johnson, Matthew, et al.
Published: (2022)

Upper Bounds on the Acyclic Chromatic Index of Degenerate Graphs
by: Anto, Nevil, et al.
Published: (2023)