Copertina

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bergougnoux, Benjamin, Jaffke, Lars
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity Data Structures and Algorithms 68Q17, 68Q25, 68Q27
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

A Polynomial-time Algorithm to Solve the Airplane Refueling Problem: the Sequential Search Algorithm
di: Cui, Jinchuan, et al.
Pubblicazione: (2022)

Parameterized Complexity of Directed Traveling Salesman Problem
di: Blažej, Václav, et al.
Pubblicazione: (2025)

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

The Separation of $NP$ and $PSPACE$
di: Lin, Tianrong
Pubblicazione: (2021)

P not equal to NP
di: Delgado, Daniel Cardona
Pubblicazione: (2023)

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

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

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

Coloring Hardness on Low Twin-Width Graphs
di: Bonnet, Édouard
Pubblicazione: (2025)

Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
di: Datta, Swarnalipa, et al.
Pubblicazione: (2026)

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

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
di: Li, Zhangsong
Pubblicazione: (2026)

Polynomial Identity Testing via Evaluation of Rational Functions
di: Hu, Ivan, et al.
Pubblicazione: (2022)

Shortest Paths without a Map, but with an Entropic Regularizer
di: Bubeck, Sébastien, et al.
Pubblicazione: (2022)

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

Efficient Algorithms for Injectivity and Bounded Surjectivity of One-dimensional Nonlinear Cellular Automata
di: Wang, Chen, et al.
Pubblicazione: (2023)

Parallel Algorithms for Group Isomorphism via Code Equivalence
di: Levet, Michael
Pubblicazione: (2026)

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

The n-vehicle exploration problem is NP-complete
di: Cui, Jinchuan, et al.
Pubblicazione: (2023)

On Solving Reachability in Grid Digraphs using a Psuedoseparator
di: Jain, Rahul, et al.
Pubblicazione: (2019)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
di: Edwards, Darren J.
Pubblicazione: (2025)

On Binary Networked Public Goods Game with Altruism
di: Maiti, Arnab, et al.
Pubblicazione: (2022)

Parameterized Algorithms for Kidney Exchange
di: Maiti, Arnab, et al.
Pubblicazione: (2021)

Unifying lower bounds for algebraic machines, semantically
di: Seiller, Thomas, et al.
Pubblicazione: (2018)

New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets
di: Liu, Bowen
Pubblicazione: (2025)

Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
di: Li, Zhangsong
Pubblicazione: (2025)

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

Exact Set Packing in Multimodal Transportation with Ridesharing System for First/Last Mile
di: Gu, Qian-Ping, et al.
Pubblicazione: (2025)

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

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
di: Ilmavirta, Joonas, et al.
Pubblicazione: (2023)

The Complexity Landscape of Two-Stage Robust Selection Problems with Budgeted Uncertainty
di: Goerigk, Marc, et al.
Pubblicazione: (2026)

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

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

Teaching and Learning under Deductive Errors
di: Telle, Jan Arne, et al.
Pubblicazione: (2026)

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