Study Of The K-Edge Induced Subgraph Problem

Solution to problems, also known as algorithm, is not only a technical term for computer science. It has been studied for thousands of years as a branch of mathematics. The emergence of the computer makes it possible to use computer simulation and to solve practical problems, and as a result of the last century computer CPU processing power limitations, memory, disk, such as a lack of resources so that people began to focus on the best ways to solve the problem. This greatly stimulated the development of algorithms for a variety of types of problems. At the same time, in order for the algorithm to be evaluated good or bad, it developed the complexity theory. It is the main method to solve the problem from the steps required is the time to run, as well as the use of additional space to evaluate the quality of the algorithm. If the algorithm is running on the algorithm's input the length of the polynomial, generally is considered to be a good algorithm. It gradually through the study found that some of the problems seem do not have a good algorithm. Even more surprising is that these problems exist, if any one of the algorithm can be a good solution, these problems can find a good algorithm. Therefore, the type of people classified as a class of problems called NP-complete, is generally believed that when a problem is NP-complete there can be no polynomial time algorithm to solve it.Graph theory is one of the oldest branches of mathematics. Graph theory and algorithm have a natural link, such as the seven bridge problem. Several of Karp's 21 basic NP-complete problems belong to graph theory. There exists a huge number of graph problem which is NP-complete, many seemed simple question is infact NP- complete.In this paper, we study the k-edge induced subgraph problem, that is, asked whether there exists an induced subgraph which contains k edge. In this paper, we prove this problem to be a difficult problem that is NP complete through a polynomial reduction. Meanwhile, this thesis also focuses on a variety categories of graphs. Both positive and negative results are given.