Maximum regular induced subgraphs in -free graphs

详细信息    查看全文

• 作者：Vadim V. Lozin ; Raffaele Mosca
• 关键词：Independent set ; Clique ; Induced matching ; Regular induced subgraph ; Polynomial-time algorithm ; 2P3-free graphs
• 刊名：Theoretical Computer Science
• 出版年：2012
• 出版时间：16 November, 2012
• 年：2012
• 卷：460
• 期：Complete
• 页码：26-33
• 全文大小：245 K

文摘

Finding maximum regular induced subgraphs is a family of algorithmic graph problems containing several important representatives such as maximum independent set, maximum clique, and maximum induced matching. These problems are generally NP-hard. On the other hand, each of them may become polynomially solvable when restricted to graphs in special classes. However, polynomial-time solutions are available only for very few monogenic classes, i.e.?classes defined by a single forbidden induced subgraph. Only three such results are available for the maximum independent set and maximum clique problems and only two for the maximum induced matching problem. In the present paper, we extend this restricted list of results by exploring the complexity of the problems in the class of -free graphs, which recently attracted considerable attention in the literature. By elaborating a polynomial-time solution to the maximum independent set problem in the class of -free graphs proposed by Farber in , we show that both maximum independent set (0-regular induced subgraph) and maximum induced matching(1-regular induced subgraph) are solvable in polynomial time for -free graphs. We also conjecture that the same is true for finding maximum -regular induced subgraphs for each value of . On the other hand, we conjecture that finding a maximum subset of vertices inducing the complement of a -regular induced subgraph is NP-hard for -free graphs and verify the conjecture for (maximum clique), (maximum induced co-matching), and .