摘要：König-Egerváry graphs form an important graph class which has been studied extensively in graph theory. Much attention has also been paid on König-Egerváry subgraphs and König-Egerváry graph modification problems. In this paper, we focus on one König-Egerváry subgraph problem, called the Maximum Edge Induced König Subgraph problem. By exploiting the classical Gallai-Edmonds decomposition, we establish connections between minimum vertex cover, Gallai-Edmonds decomposition structure, maximum matching, maximum bisection, and König-Egerváry subgraph structure. We obtain a new structural property of König-Egerváry subgraph: every graph G=(V, E) has an edge induced König-Egerváry subgraph with at least 2|E|/3 edges. Based on the new structural property proposed, an approximation algorithm with ratio 10/7 for the Maximum Edge Induced König Subgraph problem is presented, improving the current best ratio of 5/3. To the best of our knowledge, this paper is the first one establishing the connection between Gallai-Edmonds decomposition and König-Egerváry graphs. Using 2|E|/3 as a lower bound, we define the Edge Induced König Subgraph above lower bound problem, and give a kernel of at most 30k edges for the problem.
