The complexity of blocking all solutions

DOI10.1016/J.TCS.2026.115820MaRDI QIDQ6835775zbMATH OpenFDO

Authors Christoph Grüne, Lasse Wulf

Publication date 30 March 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexityrobust optimizationpolynomial hierarchyinterdiction problemsedge blockermost vital edgesblocker problemsvertex blockermost vital vertexmost vital elementsmost vital nodesnode blockersigma-2

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 3694608 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• A complexity and approximability study of the bilevel knapsack problem
• Assistance and interdiction problems on interval graphs
• Blockers for the stability number and the chromatic number
• Blocking independent sets for \(H\)-free graphs via edge contractions and vertex deletions
• Completeness in the polynomial hierarchy for many natural problems in bilevel and robust optimization
• Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems
• Complexity of determining the most vital elements for the p-median and p-center location problems
• Complexity of most vital nodes for independent set in graphs related to tree structures
• Complexity of the multilevel critical node problem
• Deterministic network interdiction
• Matching interdiction
• Minimum cost edge blocker clique problem
• Minimum edge blocker dominating set problem
• Minimum vertex blocker clique problem
• On blockers and transversals of maximum independent sets in co-comparability graphs
• On short paths interdiction problems: Total and node-wise limited interdiction
• On the hardness of covering-interdiction problems
• Propositional truth maintenance systems: Classification and complexity analysis
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• Reducing the domination number of graphs via edge contractions and vertex deletions
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The k most vital arcs in the shortest path problem
• The maximum clique interdiction problem
• The most vital edges in the minimum spanning tree problem
• The most vital nodes with respect to independent set and vertex cover
• The node-deletion problem for hereditary properties is NP-complete
• The polynomial hierarchy and a simple model for competitive analysis
• The polynomial-time hierarchy
• The trouble with the second quantifier

This page was built for publication: The complexity of blocking all solutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6835775)