2026-08-15T23:51:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9979 2024-03-06T10:45:15Z ddc:004 open_access

New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition Feng, Qilong Tan, Guanlan Zhu, Senmin Fu, Bin Wang, Jianxin König-Egerváry graph Gallai-Edmonds decomposition 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Qilong Feng and Guanlan Tan and Senmin Zhu and Bin Fu and Jianxin Wang 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.31 urn:nbn:de:0030-drops-99790 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.31 eng https://creativecommons.org/licenses/by/3.0/legalcode