2011/05/03 by Bingkai Lin, Yijia Chen, Lin, Bingkai +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1105.0477
openalex publication_date 2011/05/03 · arxiv created 2012/05/01 · arxiv updated 2012/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 [Andrews, 86], 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 [Frick and Grohe, 01]. 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 rare known examples in parameterized complexity that are easy for decision while hard for counting.