Buchumschlag

The Complexity of Blocking All Solutions

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Grüne, Christoph, Wulf, Lasse
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity Discrete Mathematics Optimization and Control F.2.2
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
von: Grüne, Christoph, et al.
Veröffentlicht: (2024)

Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
von: Grüne, Christoph, et al.
Veröffentlicht: (2023)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
von: Bartlett, Celina Janet
Veröffentlicht: (2025)

Complexity of Firefighting on Graphs
von: Althoetmar, Julius, et al.
Veröffentlicht: (2025)

On Minimum Maximal Distance-k Matchings
von: Kartynnik, Yury, et al.
Veröffentlicht: (2016)

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
von: Istrate, Gabriel
Veröffentlicht: (2024)

On Finding Randomly Planted Cliques in Arbitrary Graphs
von: Agrimonti, Francesco, et al.
Veröffentlicht: (2025)

A Decomposition Approach to the Weighted $k$-server Problem
von: Ayyadevara, Nikhil, et al.
Veröffentlicht: (2024)

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
von: Fairbairn, David L., et al.
Veröffentlicht: (2024)

On the Complexity of Problems on Graphs Defined on Groups
von: Das, Bireswar, et al.
Veröffentlicht: (2025)

Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally
von: Bok, Jan, et al.
Veröffentlicht: (2025)

On the Computational Complexity of Multi-Objective Ordinal Unconstrained Combinatorial Optimization
von: Figueira, José Rui, et al.
Veröffentlicht: (2024)

Relaxation strength for multilinear optimization: McCormick strikes back
von: Schutte, Emily, et al.
Veröffentlicht: (2023)

On the complexity of a maintenance problem for hierarchical systems
von: Schulz, Andreas S., et al.
Veröffentlicht: (2023)

Induced Disjoint Paths Without an Induced Minor
von: Aboulker, Pierre, et al.
Veröffentlicht: (2025)

On the hull and interval numbers of oriented graphs
von: Araujo, J., et al.
Veröffentlicht: (2022)

Prophet Inequalities: Separating Random Order from Order Selection
von: Giambartolomei, Giordano, et al.
Veröffentlicht: (2023)

APTAS for bin packing with general cost structures
von: Jaykrishnan, G., et al.
Veröffentlicht: (2024)

IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates
von: Giambartolomei, Giordano, et al.
Veröffentlicht: (2024)

Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives
von: Asadi, Ali, et al.
Veröffentlicht: (2025)

The Gallai Vertex Problem is $Θ_2^p$-Complete
von: Nikabadi, Amir, et al.
Veröffentlicht: (2026)

The connected Grundy coloring problem: Formulations and a local-search enhanced biased random-key genetic algorithm
von: Silva, Mateus C., et al.
Veröffentlicht: (2024)

Gromov's Approximating Tree and the All-Pairs Bottleneck Paths Problem
von: Cornect, Anders, et al.
Veröffentlicht: (2024)

Sum-of-squares lower bounds for Non-Gaussian Component Analysis
von: Diakonikolas, Ilias, et al.
Veröffentlicht: (2024)

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
von: Pavlov, Gorgi
Veröffentlicht: (2026)

On the complexity of Sandwich Problems for $M$-partitions
von: Barsukov, Alexey, et al.
Veröffentlicht: (2026)

The vehicle routing problem with synchronization constraints and support vehicle-dependent service times
von: Wittwer, David, et al.
Veröffentlicht: (2024)

Diffusion-Robust Optimization over Graphs
von: Aolaritei, Liviu, et al.
Veröffentlicht: (2026)

Approximate Graph Colouring and the Crystal with a Hollow Shadow
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2022)

The Complexity of Graph Exploration Games
von: Fuchs, Janosch, et al.
Veröffentlicht: (2023)

A Parametrized Complexity View on Robust Scheduling with Budgeted Uncertainty
von: Goldberg, Noam, et al.
Veröffentlicht: (2026)

Mim-Width is paraNP-complete
von: Bergougnoux, Benjamin, et al.
Veröffentlicht: (2025)

Answering Related Questions
von: Bonnet, Édouard
Veröffentlicht: (2025)

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
von: Anand, Emile
Veröffentlicht: (2025)

Coloring Hardness on Low Twin-Width Graphs
von: Bonnet, Édouard
Veröffentlicht: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
von: Bonnet, Édouard
Veröffentlicht: (2024)

Neural Networks and (Virtual) Extended Formulations
von: Hertrich, Christoph, et al.
Veröffentlicht: (2024)

Price Optimal Routing in Public Transportation
von: Euler, Ricardo, et al.
Veröffentlicht: (2022)

Arithmetic Circuits and Neural Networks for Regular Matroids
von: Hertrich, Christoph, et al.
Veröffentlicht: (2025)

Stable Set Polytopes with Rank $|V(G)|/3$ for the Lovász--Schrijver SDP Operator
von: Au, Yu Hin, et al.
Veröffentlicht: (2025)