Cover Image

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Avila, Tatiana Rocha, Brinkmann, Julian Christoph, Leonhardt, Alexander, Schecker, Conrad
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity 68Q25, 68R10
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Cluster Vertex Deletion Problems on Cubic Graphs
by: Rusu, Irena
Published: (2025)

The Complexity of Resilience for Digraph Queries
by: Bodirsky, Manuel, et al.
Published: (2026)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

Regenerative Ulam-von Neumann Algorithm: An Innovative Markov chain Monte Carlo Method for Matrix Inversion
by: Ghosh, Soumyadip, et al.
Published: (2024)

Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases
by: Meusel, Julia, et al.
Published: (2025)

Shortest Paths in a Weighted Simplicial Complex
by: Chakraborty, Sukrit, et al.
Published: (2025)

A Morse-Bott Framework for Blind Inverse Problems: Local Recovery Guarantees and the Failure of the MAP
by: Nguyen, Minh-Hai, et al.
Published: (2025)

Which graph motif parameters count?
by: Bläser, Markus, et al.
Published: (2025)

Compression with wildcards: All models of a Boolean 2-CNF
by: Wild, Marcel
Published: (2012)

ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
by: MIT Hardness Group, et al.
Published: (2024)

Linear average-case complexity of algorithmic problems in groups
by: Olshanskii, Alexander, et al.
Published: (2022)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

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

Some derivations among Logarithmic Space Bounded Counting Classes
by: Janaki, V., et al.
Published: (2023)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Dead Zones Enable Flexible Phase Organization in Coupled Oscillators
by: Akhavan, Naghmeh, et al.
Published: (2026)

A space-time dual-pairing summation-by-parts framework for forward and adjoint wave equations
by: Wiratama, Kenny, et al.
Published: (2026)

Haar Wavelets, Gradients and Approximate TV Regularization
by: Sauer, Tomas, et al.
Published: (2022)

Commutator-free Cayley methods
by: Maslovskaya, Sofya, et al.
Published: (2024)

A Second-Order TGV Discretization with $90^{\circ}$ Rotational Invariance Property
by: Hosseini, Alireza, et al.
Published: (2022)

Mixed finite element methods for linear Cosserat equations
by: Boon, Wietse Marijn, et al.
Published: (2024)

Entropy stable finite difference methods via entropy correction artificial viscosity and knapsack limiting
by: Christner, Brian, et al.
Published: (2025)

Robust First and Second-Order Differentiation for Regularized Optimal Transport
by: Li, Xingjie, et al.
Published: (2024)

An Efficient Two-Sided Sketching Method for Large-Scale Tensor Decomposition Based on Transformed Domains
by: Cheng, Zhiguang, et al.
Published: (2024)

Gripenberg-like algorithm for the lower spectral radius
by: Guglielmi, Nicola, et al.
Published: (2024)

A study of ferronematic thin films including a stray field energy
by: Dutta, Shilpa, et al.
Published: (2025)

PCA++: How Uniformity Induces Robustness to Background Noise in Contrastive Learning
by: Wu, Mingqi, et al.
Published: (2025)

Scattering from a random thin coating of nanoparticles: the Dirichlet case
by: Boucart, Amandine, et al.
Published: (2025)

Micro-Macro Coupling for Optimizing Scaffold Mediated Bone Regeneration
by: Dondl, Patrick, et al.
Published: (2025)

Optimal Hardness of Online Algorithms for Large Independent Sets
by: Gamarnik, David, et al.
Published: (2025)

No Constant-Cost Protocol for Point--Line Incidence
by: Göös, Mika, et al.
Published: (2026)

Complexity of Sequence-to-Graph Alignment with Co-Linear Chaining
by: Li, Xingfu
Published: (2026)

On the Low Weight Polynomial Multiple Problem
by: Ţiplea, Ferucio Laurenţiu, et al.
Published: (2024)

A polynomial-time algorithm for deciding the Hilbert Nullstellensatz over $\mathbb{Z}_2$. A proof of $\mathbf{P}=\mathbf{NP}$ hypothesis
by: Petrov, Petar P.
Published: (2022)

The Word Problem for Products of Symmetric Groups
by: Simon, Hans U.
Published: (2025)

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)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

The Complexity of Iterated Reversible Computation
by: Eppstein, David
Published: (2021)