The parameterized complexity of k-edge induced subgraphs

详细信息    查看全文

• 作者：Bingkai Lin^a ; ^{lin@is.s.u-tokyo.ac.jp} ; Yijia Chen^b ; ^{yijiachen@fudan.edu.cn}
• 关键词：k-Edge induced subgraph ; Fixed-parameter tractable ; #W[1]#W[1]-hard
• 刊名：Information and Computation
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：252
• 期：Complete
• 页码：138-160
• 全文大小：593 K
• 卷排序：252

文摘

We prove that finding a k-edge induced subgraph is fixed-parameter tractable, thereby answering an open problem of Leizhen Cai. Our algorithm is based on several combinatorial observations, Gauss' famous Eureka theorem, and a generalization of the well-known fpt-algorithm for the model-checking problem for first-order logic on graphs with locally bounded tree-width due to Frick and Grohe. On the other hand, we show that two natural counting versions of the problem are hard. Hence, the k-edge induced subgraph problem is one of the very few known examples in parameterized complexity that are easy for decision while hard for counting.