Image de couverture de livre

An Invitation to "Fine-grained Complexity of NP-Complete Problems"

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Nederlof, Jesper
Format:	Preprint
Publié:	2026
Sujets:	Data Structures and Algorithms Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
par: Kluk, Kacper, et autres
Publié: (2025)

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
par: Björklund, Andreas, et autres
Publié: (2025)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
par: Kisfaludi-Bak, Sándor, et autres
Publié: (2020)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
par: Gaspers, Serge, et autres
Publié: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
par: Kleinberg, Robert, et autres
Publié: (2026)

Recognizing Sumsets is NP-Complete
par: Abboud, Amir, et autres
Publié: (2024)

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
par: Zhang, Bingwei, et autres
Publié: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
par: Guruswami, Venkatesan, et autres
Publié: (2023)

Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
par: Nederlof, Jesper
Publié: (2025)

The Fine-Grained Complexity of Episode Matching
par: Bille, Philip, et autres
Publié: (2021)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
par: Rohwedder, Lars, et autres
Publié: (2024)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
par: Chudigiewitsch, Florian, et autres
Publié: (2026)

Complexity of Local Search for Euclidean Clustering Problems
par: Manthey, Bodo, et autres
Publié: (2023)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
par: Gaikwad, Ajinkya, et autres
Publié: (2025)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
par: Shih, Yu-Sheng, et autres
Publié: (2026)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
par: Focke, Jacob, et autres
Publié: (2023)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
par: Lehner, Lisa, et autres
Publié: (2025)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

Kernelization Complexity of Solution Discovery Problems
par: Grobler, Mario, et autres
Publié: (2024)

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
par: Chia, Nai-Hui, et autres
Publié: (2026)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
par: Foucaud, Florent, et autres
Publié: (2023)

A Simple Proof that Ricochet Robots is PSPACE-Complete
par: Balanza-Martinez, Jose, et autres
Publié: (2024)

Fine-grained Meta-Theorems for Vertex Integrity
par: Lampis, Michael, et autres
Publié: (2021)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
par: Mu, Ta-Yu, et autres
Publié: (2024)

Sorting by Strip Swaps is NP-Hard
par: Roy, Swapnoneel, et autres
Publié: (2025)

Fine-Grained Complexity of Continuous Euclidean k-Center
par: Blank, Lotte, et autres
Publié: (2026)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
par: Ducoffe, Guillaume
Publié: (2026)

Computational-Statistical Tradeoffs from NP-hardness
par: Blanc, Guy, et autres
Publié: (2025)

Fine-Grained Classification Of Detecting Dominating Patterns
par: Dransfeld, Jonathan, et autres
Publié: (2025)

Scheduling Problems with Constrained Rejections
par: Davies, Sami, et autres
Publié: (2025)

Neighborhood-Aware Graph Labeling Problem
par: Shahverdikondori, Mohammad, et autres
Publié: (2026)

String Consensus Problems with Swaps and Substitutions
par: Gabory, Estéban, et autres
Publié: (2025)

Equivalent Instances for Scheduling and Packing Problems
par: Jansen, Klaus, et autres
Publié: (2025)

Pseudodeterministic Algorithms for Minimum Cut Problems
par: Agarwala, Aryan, et autres
Publié: (2025)

Parameterized Complexity of Vehicle Routing
par: Döring, Michelle, et autres
Publié: (2025)

The Complexity of Finding and Counting Subtournaments
par: Döring, Simon, et autres
Publié: (2025)

On the Parameterized Complexity of Odd Coloring
par: Bhyravarapu, Sriram, et autres
Publié: (2025)

On the Complexity of Signed Roman Domination
par: Reddy, Sangam Balchandar
Publié: (2025)

On the Space Complexity of Online Convolution
par: Andersson, Joel Daniel, et autres
Publié: (2025)

Computational Complexity in Property Testing
par: Pinto Jr., Renato Ferreira, et autres
Publié: (2025)