Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950633 | Information and Computation | 2017 | 23 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Bingkai Lin, Yijia Chen,