加载中…
For a graph , the -free Edge Deletion problem asks whether there exist at most edges whose deletion from the input graph results in a graph without any induced copy of . We prove that -free Edge Deletion is NP-complete if is a graph with at least two edges and has a component with maximum number of vertices which is a tree or a regular graph. Furthermore, we obtain that these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time , unless Exponential Time Hypothesis fails.

生成讲解博客的中文版本

生成AI智能校验的中文版本