The Parameterized Complexity Of K-Edge Induced Subgraphs

We prove that fnding a k-edge induced subgraph is fxed-parameter tractable,thereby answering an open problem of Leizhen Cai [2]. More specifcally, we provethat for any given k, we can construct a linear time algorithm that decides a graph Ghas a k-edge induced subgraph. Our algorithm is based on some Ramesey type results,Gauss’ famous Eureka theorem [1], and an algorithmic-meta theorem.On the otherhand, we prove that k-edge induced subgraph is NP-Complete on simple graphs andW[1]-hard on graphs with multiedges.