The parameterized complexity of editing graphs for bounded degeneracy

作     者：Mathieson, Luke 

作者机构：Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2010年第411卷第34-36期

页      面：3181-3187页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Combinatorial problems Computational complexity Parameterized complexity Degenerate graphs Graph editing 

摘      要：We examine the parameterized complexity of the problem of editing a graph to obtain an r-degenerate graph. We show that for the editing operations vertex deletion and edge deletion, both separately and combined, the problem is W[P]-complete. and remains W[P]-complete even if the input graph is already (r + 1)-degenerate, or has maximum degree 2r + 1 for all r = 2. We also demonstrate fixed-parameter tractability for several CLIQUE based problems when the input graph has bounded degeneracy. (C) 2010 Elsevier B.V. All rights reserved.