License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.31
URN: urn:nbn:de:0030-drops-99790
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9979/
Feng, Qilong ;
Tan, Guanlan ;
Zhu, Senmin ;
Fu, Bin ;
Wang, Jianxin
New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition
Abstract
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.
BibTeX - Entry
@InProceedings{feng_et_al:LIPIcs:2018:9979,
author = {Qilong Feng and Guanlan Tan and Senmin Zhu and Bin Fu and Jianxin Wang},
title = {{New Algorithms for Edge Induced K{\"o}nig-Egerv{\'a}ry Subgraph Based on Gallai-Edmonds Decomposition}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {31:1--31:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-094-1},
ISSN = {1868-8969},
year = {2018},
volume = {123},
editor = {Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9979},
URN = {urn:nbn:de:0030-drops-99790},
doi = {10.4230/LIPIcs.ISAAC.2018.31},
annote = {Keywords: K{\"o}nig-Egerv{\'a}ry graph, Gallai-Edmonds decomposition}
}
|
Keywords: |
|
König-Egerváry graph, Gallai-Edmonds decomposition |
|
Collection: |
|
29th International Symposium on Algorithms and Computation (ISAAC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
06.12.2018 |
