A Parameterized Complexity View on Collapsing k-Cores

doi:10.1007/s00224-021-10045-w

CSpace

	A Parameterized Complexity View on Collapsing k-Cores
	Luo, Junjie 1,2,3; Molter, Hendrik 1; Suchy, Ondrej 4
	2021-06-19
发表期刊	THEORY OF COMPUTING SYSTEMS
ISSN	1432-4350
页码	40
摘要	We study the NP-hard graph problem Collapsed k-Core where, given an undirected graph G and integers b, x, and k, we are asked to remove b vertices such that the k-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degree k, has size at most x. Collapsed k-Core was introduced by Zhang et al. (2017) and it is motivated by the study of engagement behavior of users in a social network and measuring the resilience of a network against user drop outs. Collapsed k-Core is a generalization of r-Degenerate Vertex Deletion (which is known to be NP-hard for all r >= 0) where, given an undirected graph G and integers b and r, we are asked to remove b vertices such that the remaining graph is r-degenerate, that is, every its subgraph has minimum degree at most r. We investigate the parameterized complexity of Collapsed k-Core with respect to the parameters b, x, and k, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity of Collapsed k-Core for k <= 2 and k >= 3. For the latter case it is known that for all x >= 0 Collapsed k-Core is W[P]-hard when parameterized by b. For k <= 2 we show that Collapsed k-Core is W[1]-hard when parameterized by b and in FPT when parameterized by (b + x). Furthermore, we outline that Collapsed k-Core is in FPT when parameterized by the treewidth of the input graph and presumably does not admit a polynomial kernel when parameterized by the vertex cover number of the input graph.
关键词	r-Degenerate vertex deletion Feedback vertex set Fixed-parameter tractability Kernelization lower bounds Graph algorithms Social network analysis
DOI	10.1007/s00224-021-10045-w
收录类别	SCI
语种	英语
资助项目	Projekt DEAL
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Theory & Methods ; Mathematics
WOS记录号	WOS:000663468900002
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/58825
专题	中国科学院数学与系统科学研究院
通讯作者	Luo, Junjie
作者单位	1.TU Berlin, Fac 4, Algorithm & Computat Complex, Berlin, Germany 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China 3.Univ Chinese Acad Sci, Sch Math Sci, Beijing, Peoples R China 4.Czech Tech Univ, Fac Informat Technol, Dept Theoret Comp Sci, Prague, Czech Republic
推荐引用方式 GB/T 7714	Luo, Junjie,Molter, Hendrik,Suchy, Ondrej. A Parameterized Complexity View on Collapsing k-Cores[J]. THEORY OF COMPUTING SYSTEMS,2021:40.
APA	Luo, Junjie,Molter, Hendrik,&Suchy, Ondrej.(2021).A Parameterized Complexity View on Collapsing k-Cores.THEORY OF COMPUTING SYSTEMS,40.
MLA	Luo, Junjie,et al."A Parameterized Complexity View on Collapsing k-Cores".THEORY OF COMPUTING SYSTEMS (2021):40.