2026-07-23T13:07:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6443 2024-03-06T10:38:17Z ddc:004 open_access

Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs Datta, Samir Kulkarni, Raghav Mukherjee, Anish maximum matching approximation scheme logspace planar graphs We present a Logspace Approximation Scheme (LSAS), i.e. an approximation algorithm for maximum matching in planar graphs (not necessarily bipartite) that achieves an approximation ratio arbitrarily close to one, using only logarithmic space. This deviates from the well known Baker's approach for approximation in planar graphs by avoiding the use of distance computation - which is not known to be in Logspace. Our algorithm actually works for any "recursively sparse" graph class which contains a linear size matching and also for certain other classes like bounded genus graphs. The scheme is based on an LSAS in bounded degree graphs which are not known to be amenable to Baker's method. We solve the bounded degree case by parallel augmentation of short augmenting paths. Finding a large number of such disjoint paths can, in turn, be reduced to finding a large independent set in a bounded degree graph. The bounded degree assumption allows us to obtain a Logspace algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Samir Datta and Raghav Kulkarni and Anish Mukherjee 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.28 urn:nbn:de:0030-drops-64436 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.28 eng https://creativecommons.org/licenses/by/3.0/legalcode