Cover Image

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	MIT Hardness Group, Hendrickson, Della, Tockman, Andy
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
by: MIT Hardness Group, et al.
Published: (2026)

Tetris is Hard with Just One Piece Type
by: MIT Hardness Group, et al.
Published: (2026)

Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
by: MIT Hardness Group, et al.
Published: (2025)

Tetris with Few Piece Types
by: MIT Hardness Group, et al.
Published: (2024)

Complexity of 2D Snake Cube Puzzles
by: MIT Hardness Group, et al.
Published: (2024)

PSPACE-Hard 2D Super Mario Games: Thirteen Doors
by: MIT Hardness Group, et al.
Published: (2024)

Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
by: MIT Gadgets Group, et al.
Published: (2020)

You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
by: MIT Hardness Group, et al.
Published: (2024)

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

Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
by: Ani, Hayashi, et al.
Published: (2024)

The Parameterized Complexity of Geometric 1-Planarity
by: Firbas, Alexander
Published: (2026)

Parameterised Complexity of Consistent Query Answering via Graph Representations
by: Hankala, Teemu, et al.
Published: (2024)

Feedback Set Problems on Bounded-Degree (Planar) Graphs
by: Bai, Tian, et al.
Published: (2026)

Linear Planar 3-SAT and Its Applications in Planning
by: Desbois, Victorien, et al.
Published: (2025)

The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
by: Asimi, Kristina, et al.
Published: (2024)

Complexity Theory for Quantum Promise Problems
by: Chia, Nai-Hui, et al.
Published: (2024)

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
by: Cai, Jin-Yi, et al.
Published: (2026)

Maximum Reachability Orientation of Mixed Graphs
by: Hörsch, Florian
Published: (2025)

Dynamic Planar Graph Isomorphism is in DynFO
by: Datta, Samir, et al.
Published: (2026)

On the Usefulness of Promises
by: Austrin, Per, et al.
Published: (2025)

Nonogram: Complexity of Inference and Phase Transition Behavior
by: Foote, Aaron, et al.
Published: (2025)

Geometry Matters in Planar Storyplans
by: Dobler, Alexander, et al.
Published: (2025)

On the Nature and Complexity of an Impartial Two-Player Variant of the Game Lights-Out
by: Fiorini, Eugene, et al.
Published: (2024)

The Computational Complexity of Factored Graphs
by: Gupta, Shreya, et al.
Published: (2024)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
by: Baril, Ambroise, et al.
Published: (2025)

New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
by: Fan, Austen, et al.
Published: (2026)

The Parameterized Complexity of Coloring Mixed Graphs
by: Lauerbach, Antonio, et al.
Published: (2026)

On the Complexity of Problems on Tree-structured Graphs
by: Bodlaender, Hans L., et al.
Published: (2022)

Hexasort -- The Complexity of Stacking Colors on Graphs
by: Klocker, Linus, et al.
Published: (2026)

On the Complexity of Vertex-Splitting Into an Interval Graph
by: Abu-Khzam, Faisal N., et al.
Published: (2026)

Super Unique Tarski is in UEOPL
by: Fearnley, John, et al.
Published: (2024)

Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
by: Liu, Brian, et al.
Published: (2024)

The Complexity of Contracting Bipartite Graphs into Small Cycles
by: Krithika, R., et al.
Published: (2022)

On the Parameterized Complexity of Semitotal Domination on Graph Classes
by: Retschmeier, Lukas
Published: (2025)

Strong Inapproximability for a Promise Rank Problem
by: Guruswami, Venkatesan, et al.
Published: (2026)

Equations over Finite Monoids with Infinite Promises
by: Larrauri, Alberto, et al.
Published: (2025)

Recognizing 2-Layer and Outer $k$-Planar Graphs
by: Kobayashi, Yasuaki, et al.
Published: (2024)

On the Complexity of Pure-State Consistency of Local Density Matrices
by: Kamminga, Jonas, et al.
Published: (2024)

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
by: Hirahara, Shuichi, et al.
Published: (2024)