On the parameterized complexity of minimum/maximum degree vertex deletion on several special graphs
作者机构：School of Information EngineeringHunan Industry PolytechnicChangsha 410036China Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on TransportationSchool of Computer and Communication EngineeringChangsha University of Science and TechnologyChangsha 410015China Chair of Economic TheorySaarland UniversitySaarbrücken 66123Germany
出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)
年 卷 期：2023年第17卷第4期
页 面：97-107页
核心收录：
基 金：supported by the Science and Education Joint Project of Hunan Natural Science Foundation 湖南省教育厅项目 湖南省自然科学基金
主 题：minimum degree maximum degree vertex deletion split graphs planar graphs parameterized complexity
摘 要：In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum degree.The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree.It is known that both problems areΨ-hard and fixed-parameter intractable with respect to some natural parameters.In this paper,we study the(parameterized)complexity of these two problems restricted to split graphs,p-degenerate graphs,and planar graphs.Our study provides a comprehensive complexity landscape of the two problems restricted to these special graphs.
维普期刊数据库