Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number

详细信息	查看全文 | 推荐本文 |

• 作者：Konrad Dabrowski^a ; ^{k.k.dabrowski@warwick.ac.uk} ; Vadim Lozin^a ; ¹ ; ^{v.lozin@warwick.ac.uk} ; Haiko Mü ; ller^b ; ^{h.muller@leeds.ac.uk} ; Dieter Rautenbach^c ; ^{dieter.rautenbach@uni-ulm.de}
• 关键词：Independent set ; Fixed-parameter tractability ; Hereditary class of graphs ; Modular decomposition
• 刊名：Journal of Discrete Algorithms
• 出版年：2012
• 期刊代码：10_15708667
• 类别：mt
• 出版时间：July, 2012
• 卷：14
• 期：Complete
• 页码：207-213
• 文件大小：175 K

摘要

The maximum independent set problem is known to be NP-hard for graphs in general, but is solvable in polynomial time for graphs in many special classes. It is also known that the problem is generally intractable from a parameterized point of view. A simple Ramsey argument implies the fixed-parameter tractability of the maximum independent set problem in classes of graphs of bounded clique number. Beyond this observation very little is known about the parameterized complexity of the problem in restricted graph families. In the present paper we develop fpt-algorithms for graphs in some classes extending graphs of bounded clique number.