The complexity of computing minimal unidirectional covering sets

DOI10.1007/s00224-012-9437-9zbMath1286.68179arXiv0901.3692OpenAlexW3106147620MaRDI QIDQ372959

Jan Hoffmann, Jörg Rothe, Felix Fischer, Felix Brandt, Dorothea Baumeister

Publication date: 21 October 2013

Published in: Lecture Notes in Computer Science, Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0901.3692

zbMATH Keywords

computational complexitycomputational social choiceminimal downward covering setsminimal upward covering sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)

Related Items

Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games ⋮ The complexity of computing minimal unidirectional covering sets ⋮ The computational complexity of weak saddles ⋮ King-chicken choice correspondences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
• The complexity of computing minimal unidirectional covering sets
• On the possibility of reasonable consistent majoritarian choice: Some positive results
• The complexity of Kemeny elections
• Computing the minimal covering set
• A computational analysis of the tournament equilibrium set
• The complexity of facets (and some facets of complexity)
• Covering sets and a new Condorcet choice correspondence
• More complicated questions about maxima and minima, and some closures of NP
• A comparison of polynomial time reducibilities
• Relative complexity of checking and evaluating
• The polynomial-time hierarchy
• Extending Condorcet's rule
• Tournament solutions and majority voting
• Exact complexity of the winner problem for Young elections
• The minimum equivalent DNF problem and shortest implicants
• On the computational cost of disjunctive logic programming: Propositional case
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Complexity theory and cryptology. An introduction to cryptocomplexity.
• Banks winners in tournaments are difficult to recognize
• Computational Aspects of Cooperative Game Theory
• Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
• Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
• The Computational Complexity of Choice Sets
• Bounded Query Classes
• The difference and truth-table hierarchies for NP
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• Condorcet Social Choice Functions
• Exact analysis of Dodgson elections
• The Minimization Problem for Boolean Formulas
• The complexity class θp2: Recent results and applications in AI and modal logic
• Ranking Tournaments
• The Proof That a Game May Not Have a Solution