Buchumschlag

Complexity Thresholds for the Constrained Colored Token Swapping Problem

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bilò, Davide, Leucci, Stefano, Martinelli, Andrea
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
von: Bilò, Davide, et al.
Veröffentlicht: (2025)

On the approximability of graph visibility problems
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

Improved Hardness-of-Approximation for Token Swapping
von: Hiken, Sam, et al.
Veröffentlicht: (2024)

String Consensus Problems with Swaps and Substitutions
von: Gabory, Estéban, et al.
Veröffentlicht: (2025)

The Parameterized Complexity of Coloring Mixed Graphs
von: Lauerbach, Antonio, et al.
Veröffentlicht: (2026)

Hexasort -- The Complexity of Stacking Colors on Graphs
von: Klocker, Linus, et al.
Veröffentlicht: (2026)

Parameterized Complexity of the Star Decomposition Problem
von: Hajebi, Sahab, et al.
Veröffentlicht: (2024)

On the Complexity of Problems on Tree-structured Graphs
von: Bodlaender, Hans L., et al.
Veröffentlicht: (2022)

Kernelization Bounds for Constrained Coloring
von: Haviv, Ishay
Veröffentlicht: (2026)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
von: Cavalar, Bruno P., et al.
Veröffentlicht: (2025)

Scheduling Problems with Constrained Rejections
von: Davies, Sami, et al.
Veröffentlicht: (2025)

Complexity and algorithms for Swap median and relation to other consensus problems
von: Cunha, Luís, et al.
Veröffentlicht: (2024)

Computational Complexity of Edge Coverage Problem for Constrained Control Flow Graphs
von: Ruszil, Jakub, et al.
Veröffentlicht: (2026)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
von: Michno, Katzper
Veröffentlicht: (2025)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
von: Hörsch, Florian, et al.
Veröffentlicht: (2025)

The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
von: Asimi, Kristina, et al.
Veröffentlicht: (2024)

Computational Complexity of the Recoverable Robust Shortest Path Problem with Discrete Recourse
von: Jackiewicz, Marcel, et al.
Veröffentlicht: (2024)

The Complexity of Counting Turns in the Line-Based Dial-a-Ride Problem
von: Lauerbach, Antonio, et al.
Veröffentlicht: (2024)

On the Parameterized Complexity of Odd Coloring
von: Bhyravarapu, Sriram, et al.
Veröffentlicht: (2025)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
von: Grüne, Christoph
Veröffentlicht: (2022)

The Descriptive Complexity of Relation Modification Problems
von: Chudigiewitsch, Florian, et al.
Veröffentlicht: (2026)

On the Descriptive Complexity of Vertex Deletion Problems
von: Bannach, Max, et al.
Veröffentlicht: (2024)

On the Complexity of the Skolem Problem at Low Orders
von: Bacik, Piotr, et al.
Veröffentlicht: (2025)

On Extremal Properties of k-CNF: Capturing Threshold Functions
von: Gurumukhani, Mohit, et al.
Veröffentlicht: (2024)

Analogy between List Coloring Problems and the Interval $k$-$(γ,μ)$-choosability property: theoretical aspects of complexity
von: Gama, Simone Ingrid Monteiro, et al.
Veröffentlicht: (2025)

Complexity Theory for Quantum Promise Problems
von: Chia, Nai-Hui, et al.
Veröffentlicht: (2024)

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
von: Fu, Cheng-Hao, et al.
Veröffentlicht: (2025)

On the Complexity of the Succinct State Local Hamiltonian Problem
von: Waite, Gabriel, et al.
Veröffentlicht: (2025)

A Note on the Complexity of the Spectral Gap Problem
von: Yirka, Justin
Veröffentlicht: (2025)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
von: Yao, Penghui, et al.
Veröffentlicht: (2025)

Quantum Threshold is Powerful
von: Grier, Daniel, et al.
Veröffentlicht: (2024)

Sorting by Strip Swaps is NP-Hard
von: Roy, Swapnoneel, et al.
Veröffentlicht: (2025)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
von: Baril, Ambroise, et al.
Veröffentlicht: (2024)

Complexity Classification of Product State Problems for Local Hamiltonians
von: Kallaugher, John, et al.
Veröffentlicht: (2024)

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
von: Dalirrooyfard, Mina, et al.
Veröffentlicht: (2025)

The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
von: Kontogiannis, Andreas, et al.
Veröffentlicht: (2026)

Graph Spanners for Group Steiner Distances
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

Computational Complexity-Constrained Spectral Efficiency Analysis for 6G Waveforms
von: Queiroz, Saulo, et al.
Veröffentlicht: (2024)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2026)