On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion

DOI10.1016/j.jda.2015.03.002zbMath1337.68135arXiv1312.3779OpenAlexW2964207169MaRDI QIDQ491619

Ashwin Pananjady, N. Safina Devi, Sounaka Mishra

Publication date: 18 August 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmhardness of approximationnode deletion problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• A new approach for approximating node deletion problems
• Parameterized complexity of candidate control in elections and related digraph problems
• Optimization, approximation, and complexity classes
• A unified approximation algorithm for node-deletion problems
• The vertex cover \(P_3\) problem in cubic graphs
• On Making a Distinguished Vertex Minimum Degree by Vertex Deletion
• A threshold of ln n for approximating set cover
• Strong lower bounds on the approximability of some NPO PB-complete maximization problems
• Approximating k-set cover and complementary graph coloring

This page was built for publication: On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion