Cover Image

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Lobe, Elisabeth, Lutz, Annette
Format:	Preprint
Published:	2021
Subjects:	Quantum Physics Computational Complexity 68Q17, 05C83 F.2.2; G.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

DAG Scheduling in the BSP Model
by: Papp, Pál András, et al.
Published: (2023)

Graph polynomials: some questions on the edge
by: Farr, Graham, et al.
Published: (2024)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
by: Eua-anant, Pakapim, et al.
Published: (2025)

XALP-completeness of Parameterized Problems on Planar Graphs
by: Bodlaender, Hans L., et al.
Published: (2024)

Ember: An Extensible Benchmark Suite for Quantum Annealing Embedding Algorithms
by: Macaskill-Smith, Zachary, et al.
Published: (2026)

On Small-depth Frege Proofs for PHP
by: Håstad, Johan
Published: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
by: Levin, Leonid A.
Published: (2022)

Folding One Polyhedral Metric Graph into Another
by: Chung, Lily, et al.
Published: (2024)

Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars
by: Choi, Mujin, et al.
Published: (2025)

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
by: Liao, Chao, et al.
Published: (2022)

On (In)approximability of MaxMin Independent Set Reconfiguration
by: Hoang, Hung P., et al.
Published: (2026)

QuIC: A Training-Free Quantum Graph Embedding from Ideal Analysis to Practical Hardware Evaluation
by: Miller, Luke, et al.
Published: (2026)

NP-hardness of p-adic linear regression
by: Baker, Gregory D.
Published: (2026)

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

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
by: Golovach, Petr A., et al.
Published: (2022)

Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes
by: Sau, Ignasi, et al.
Published: (2026)

The Gallai Vertex Problem is $Θ_2^p$-Complete
by: Nikabadi, Amir, et al.
Published: (2026)

Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals
by: Lubiw, Anna, et al.
Published: (2025)

Evolomino is NP-complete
by: Nikolaev, Andrei V.
Published: (2025)

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

Maximum Solow--Polasky Diversity Subset Selection Is NP-hard Even in the Euclidean Plane
by: Emmerich, Michael T. M., et al.
Published: (2026)

A New Temporal Interpretation of Cluster Editing
by: Bocci, Cristiano, et al.
Published: (2022)

Computing shortest closed curves on non-orientable surfaces
by: Bulavka, Denys, et al.
Published: (2024)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Faster parameterized algorithms for modification problems to minor-closed classes
by: Morelle, Laure, et al.
Published: (2022)

Vertex identification to a forest
by: Morelle, Laure, et al.
Published: (2024)

Dominic Welsh: his work and influence
by: Farr, Graham, et al.
Published: (2024)

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

How quickly can you pack short paths? Engineering a search-tree algorithm for disjoint s-t paths of bounded length
by: Huber, Michael Kiran
Published: (2024)

A Constant-factor Approximation for Weighted Bond Cover
by: Kim, Eun Jung, et al.
Published: (2021)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
by: Demaine, Erik D., et al.
Published: (2024)

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

On Strict Brambles
by: Lardas, Emmanouil, et al.
Published: (2022)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

Identification to Subclasses of Chordal Graphs
by: Golovach, Petr A., et al.
Published: (2026)

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
by: Lagerkvist, Victor, et al.
Published: (2026)

Pliability and Approximating Max-CSPs
by: Romero, Miguel, et al.
Published: (2019)

Thin Tree Verification is coNP-Complete
by: Moayyedi, Alice
Published: (2025)

Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard
by: Emmerich, Michael T. M., et al.
Published: (2026)

Graph modification of bounded size to minor-closed classes as fast as vertex deletion
by: Morelle, Laure, et al.
Published: (2025)