Computer Science – Data Structures and Algorithms
Scientific paper
2011-05-03
Computer Science
Data Structures and Algorithms
Scientific paper
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 \emph{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.
Chen Yijia
Lin Bingkai
No associations
LandOfFree
The parameterized complexity of k-edge induced subgraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The parameterized complexity of k-edge induced subgraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The parameterized complexity of k-edge induced subgraphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-692351