:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Jost, Niklas, Escobedo, Adolfo, Kirchheim, Alice
Format:	Preprint
Published:	2025
Subjects:	Discrete Mathematics
Online Access:	https://arxiv.org/abs/2510.25614
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hierarchy of Hub Covering Problems
by: Jost, Niklas
Published: (2025)

Facet-Defining Inequalities for the Angle-Based DC Optimal Transmission Switching Formulation
by: Jabbari-Marand, Behnam, et al.
Published: (2026)

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

Crossing Number is NP-hard for Constant Path-width (and Tree-width)
by: Hliněný, Petr, et al.
Published: (2024)

Weighted Treedepth is NP-complete on Graphs of Bounded Degree
by: Dirks, Jona, et al.
Published: (2025)

A note on hardness of promise hypergraph colouring
by: Wrochna, Marcin
Published: (2022)

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

Graceful coloring is computationally hard
by: Antony, Cyriac, et al.
Published: (2024)

Algorithms and hardness for Metric Dimension on digraphs
by: Dailly, Antoine, et al.
Published: (2023)

Fixed-parameter tractability and hardness for Steiner rooted and locally connected orientations
by: Bérczi, Kristóf, et al.
Published: (2025)

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

On expectations and variances in the hard-core model on bounded degree graphs
by: Davies, Ewan, et al.
Published: (2025)

Bakry-Émery-Ricci curvature: An alternative network geometry measure in the expanding toolbox of graph Ricci curvatures
by: Mondal, Madhumita, et al.
Published: (2024)

Recognizing Sumsets is NP-Complete
by: Abboud, Amir, et al.
Published: (2024)

Chemically inspired Erdős-Rényi oriented hypergraphs
by: Garcia-Chung, Angel, et al.
Published: (2023)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
by: Hellmuth, Marc, et al.
Published: (2023)

Reducibility among NP-Hard graph problems and boundary classes
by: Hassan, Syed Mujtaba, et al.
Published: (2024)

On 3-Connected Cubic Planar Graphs and their Strong Embeddings on Orientable Surfaces
by: Weiß, Meike, et al.
Published: (2025)

On 3-Connected Planar Graphs with Unique Orientable Circuit Double Covers
by: Weiß, Meike, et al.
Published: (2026)

On the hardness of recognizing graphs of small mim-width and its variants
by: la Tour, Max Dupré, et al.
Published: (2025)

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

Benders decomposition for congested partial set covering location with uncertain demand
by: Calamita, Alice, et al.
Published: (2024)

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

Recoverable systems and the maximal hard-core model on the triangular lattice
by: Wang, Geyang, et al.
Published: (2026)

Loop corrections for hard spheres in Hamming space
by: Ramezanpour, Abolfazl, et al.
Published: (2024)

Why Linear Programming cannot solve large instances of NP-complete problems in polynomial time
by: Hofman, Radoslaw
Published: (2006)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
by: Foucaud, Florent, et al.
Published: (2023)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2024)

The maximal hard-core model as a recoverable system: Gibbs measures and phase coexistence
by: Wang, Geyang, et al.
Published: (2025)

An NP-hardness result for the colored constrained maximum 2-edge-colorable subgraph problem in bipartite graphs
by: Mkrtchyan, Vahan
Published: (2024)

Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs
by: Kutner, David C., et al.
Published: (2025)

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
by: Istrate, Gabriel
Published: (2024)

Space-time reversible graph rewriting
by: Arrighi, Pablo, et al.
Published: (2025)

Mathematical and computational perspectives on the Boolean and binary rank and their relation to the real rank
by: Parnas, Michal
Published: (2026)

Boxicity of Zero Divisor Graphs
by: Chandran, L. Sunil, et al.
Published: (2025)

Pairwise similarity method for majority domination problem
by: Shushko, N. I., et al.
Published: (2025)

Stereotype graph: A mathematical framework of category stereotypes via graph theory
by: Yan, Yijia
Published: (2025)

Efficient Algorithms for Minimizing the Kirchhoff Index via Adding Edges
by: Zhou, Xiaotian, et al.
Published: (2025)

Temporal Orienteering with Changing Fuel Costs
by: Corsini, Timothée, et al.
Published: (2025)

Spectral Moment of Order Four and the Uniqueness of the CCZ class of Dublin APN Permutation
by: Gillot, Valérie, et al.
Published: (2025)