On the Complexity of Making a Distinguished Vertex Minimum or Maximum Degree by Vertex Deletion

Sounaka Mishra, Ashwin Pananjady, N Safina Devi

In this paper, we investigate the approximability of two node deletion problems. Given a vertex weighted graph $G=(V,E)$ and a specified, or "distinguished" vertex $p\in V$, MDD(m…