New algorithms for edge induced König-Egerváry subgraph based on Gallai-Edmonds decomposition. (English) Zbl 1535.05247
Hsu, Wen-Lian (ed.) et al., 29th international symposium on algorithms and computation, ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 123, Article 31, 12 p. (2018).
Summary: 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.
For the entire collection see [Zbl 1407.68036].
For the entire collection see [Zbl 1407.68036].
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | John A.Bondy and U. S. R. Murty. Graph Theory with Applications. North Holland, 1976. · Zbl 1226.05083 |
| [2] | Miklós Bartha and Miklós Krész. Molecular Switching by Turing Automata. In Proceedings of 3rd Workshop on Non-Classical Models for Automata and Application(NCMA), pages 51-71, 2011. · Zbl 1260.68144 |
| [3] | Francis Bloch, Bhaskar Dutta, and Mihai Manea. Efficient Partnership Formation In Net-works. Warwick Economics Research Paper, 2018. · Zbl 1427.91204 |
| [4] | Flavia Bonomo, Mitre C. Dourado, Guillermo Durán, Luerbio Faria, Luciano N. Grippo, and Martín D. Safe. Forbidden subgraphs and the König-Egerváry property. Discrete Applied Mathematics, 161(16-17):2380-2388, 2013. · Zbl 1285.05127 |
| [5] | Jean Marie. Bourjolly and William R. Pulleyblank. König-Egerváry graphs, 2-bicritical raphs and fractional matchings. Discrete Applied Mathematics, 24(1):63-82, 1989. · Zbl 0684.05036 |
| [6] | Q. Feng, G. Tan, S. Zhu, B. Fu, and J. Wang 31:11 |
| [7] | Domingos M. Cardoso, Maria Robbiano, and Oscar Rojo. Combinatorial and spectral properties of König-Egerváry graphs. Discrete Applied Mathematics, 217:446-454, 2017. · Zbl 1358.05171 |
| [8] | Jianer Chen and I. A. Kanj. Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. Journal of Computer and System Sciences, 67(4):833-847, 2003. · Zbl 1091.68076 |
| [9] | Jianer Chen, I A. Kanj, and Ge Xia. Improved parameterized upper bounds for vertex cover. In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science(MFCS), pages 238-249, 2006. · Zbl 1132.68421 |
| [10] | Marek Cygan, Marcin Pilipczuk, and Jakub Onufry. Wojtaszczyk. On multiway cut para-meterized above lower bounds. ACM Transactions on Computation Theory, 5(1):1-11, 2013. · Zbl 1322.68098 |
| [11] | Robert W. Deming. Independence numbers of graphs-an extension of the König-Egerváry theorem. Discrete Mathematics, 27(1):23-33, 1979. · Zbl 0404.05034 |
| [12] | Zakir Deniz, Tınaz Ekim, Tatiana Romina. Hartinger, Martin Milanič, and Mordechai Shalom. On two extensions of equimatchable graphs. Discrete Optimization, 26:112-130, 2017. · Zbl 1387.05194 |
| [13] | Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17(3):449-467, 1965. · Zbl 0132.20903 |
| [14] | Qilong Feng, Senmin Zhu, and Jianxin Wang. A New Kernel for Parameterized Max-Bisection Above Tight Lower Bound. In Proceedings of the 23rd Annual International Computing and Combinatorics Conference(COCOON), pages 188-199, 2017. · Zbl 1433.68179 |
| [15] | Toshihiro Fujito and Hiroshi Nagamochi. A 2-approximation algorithm for the minimum weight edge dominating set problem. Discrete Applied Mathematics, 118(3):199-207, 2002. · Zbl 1016.68061 |
| [16] | Shivam Garg and Geevarghese Philip. Raising the bar for vertex cover: fixed-parameter tractability above a higher guarantee. In Proceedings of the 27th annual ACM-SIAM Sym-posium on Discrete Algorithms(SODA), pages 1152-1166, 2016. · Zbl 1398.68234 |
| [17] | David J. Haglin and Shankar M. Venkatesan. Approximation and intractability results for the maximum cut problem and its variants. IEEE Transactions on Computers, 40(1):110-113, 1991. · Zbl 1395.68139 |
| [18] | Adi Jarden, Vadim E. Levit, and Eugen Mandrescu. Two more characterizations of König-Egerváry graphs. Discrete Applied Mathematics, 231:175-180, 2017. · Zbl 1369.05162 |
| [19] | Bo Ji and Yu Sang. Throughput characterization of node-based scheduling in multihop wireless networks: A novel application of the gallai-edmonds structure theorem. In Pro-ceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc), pages 41-50, 2016. |
| [20] | Richard M. Karp. Reducibility Among Combinatorial Problems. In Proceedings of a sym-posium on the Complexity of Computer Computations, pages 85-103, 1972. · Zbl 1467.68065 |
| [21] | Ephraim Korach, Thanh Nguyen, and Britta Peis. Subgraph characterization of red/blue-split graph and kőnig egerváry graphs. In Proceedings of the 17th annual ACM-SIAM Symposium on Discrete Algorithm(SODA), pages 842-850, 2006. · Zbl 1192.05116 |
| [22] | Stefan Kratsch. A randomized polynomial kernelization for vertex cover with a smaller parameter. arXiv preprint, 2016. arXiv:1611.06795. · Zbl 1397.68103 |
| [23] | Michael Lampis. A kernel of order 2k-clogk for vertex cover. Information Processing Letters, 111(23-24):1089-1091, 2011. · Zbl 1260.05165 |
| [24] | Vadim E. Levit and Eugen Mandrescu. Critical independent sets and König-Egerváry graphs. Graphs and Combinatorics, 28(2):243-250, 2012. · Zbl 1256.05172 |
| [25] | Vadim E. Levit and Eugen Mandrescu. On maximum matchings in König-Egerváry graphs. Discrete Applied Mathematics, 161(10-11):1635-1638, 2013. · Zbl 1287.05119 |
| [26] | Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster parameterized algorithms using linear programming. ACM Transactions on Algorithms, 11(2):15, 2014. · Zbl 1398.68254 |
| [27] | László Lovász. Ear-decompositions of matching-covered graphs. Combinatorica, 3(1):105-117, 1983. · Zbl 0516.05047 |
| [28] | László Lovász and Michael D. Plummer. Matching Theory. North-Holland, Amsterdam, 1986. · Zbl 0618.05001 |
| [29] | Eric Mcdermid. A 3/2-approximation algorithm for general stable marriage. In Proceedings of the 36th International Colloquium on Automata, Languages, and Programming(ICALP), pages 689-700, 2009. · Zbl 1248.68564 |
| [30] | Sounaka Mishra, Shijin Rajakrishnan, and Saket Saurabh. On approximability of optimiza-tion problems related to Red/Blue-split graphs. Theoretical Computer Science, 690:104-113, 2017. · Zbl 1372.68141 |
| [31] | Sounaka Mishra, Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. König deletion sets and vertex covers above the matching size. In Proceedings of the 19th International Symposium on Algorithms and Computation(ISAAC), pages 836-847, 2008. · Zbl 1183.68313 |
| [32] | Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar, and C. R. Sub-ramanian. The complexity of finding subgraphs whose matching number equals the vertex cover number. In Proceedings of the 18th International Symposium on Algorithms and Computation(ISAAC), pages 268-279, 2007. · Zbl 1193.05133 |
| [33] | Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar, and C. R. Sub-ramanian. The complexity of König subgraph problems and above-guarantee vertex cover. Algorithmica, 61(4):857-881, 2011. · Zbl 1243.05203 |
| [34] | Matthias Mnich and Rico Zenklusen. Bisections above tight lower bounds. In Proceedings of the 38th International Workshop on Graph-Theoretic Concepts in Computer Science(WG), pages 184-193, 2012. · Zbl 1341.05214 |
| [35] | N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. LP can be a cure for parameterized problems. In Proceedings of the 29th Internatinal Symposium on Theoretical Aspects of Computer Science(STACS)), pages 338-349, 2012. · Zbl 1245.68111 |
| [36] | Ojas Parekh. Edge dominating and hypomatchable sets. In Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms(SODA), pages 287-291, 2002. · Zbl 1093.68625 |
| [37] | Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Paths, flowers and vertex cover. In Proceedings of the 19th Annual European Symposium on Algorithms(ESA), pages 382-393, 2011. · Zbl 1346.05287 |
| [38] | Igor Razgon and Barry O’Sullivan. Almost 2-SAT is fixed-parameter tractable. Journal of Computer and System Sciences, 75(8):435-450, 2009. · Zbl 1184.68477 |
| [39] | Tayfun Sönmez and M Utku. Ünver. Altruistically unbalanced kidney exchange. Journal of Economic Theory, 152:105-129, 2014. · Zbl 1297.91120 |
| [40] | F. Stersoul. A characterization of the graphs in which the transversal number equals the matching number. Journal of Combinatorial Theory, Series B, 27(2):228-229, 1979. · Zbl 0415.05032 |
| [41] | C. R. Subramanian. Vertex covers: parameterizing above the requirement. IMSc Technical Report, 2001. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
