The parameterized complexity of k-edge induced subgraphs

Details The parameterized complexity of k-edge induced subgraphs The parameterized complexity of k-edge induced subgraphs

2011-05-03

arxiv.org/abs/1105.0477v2

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-692351