TY - GEN
T1 - Towards a unified theory of sparsification for matching problems
AU - Assadi, Sepehr
AU - Bernstein, Aaron
N1 - Publisher Copyright:
© Sepehr Assadi and Aaron Bernstein.
PY - 2019/1
Y1 - 2019/1
N2 - In this paper, we present a construction of a “matching sparsifier”, that is, a sparse subgraph of the given graph that preserves large matchings approximately and is robust to modifications of the graph. We use this matching sparsifier to obtain several new algorithmic results for the maximum matching problem: ⁃ An almost (3/2)-approximation one-way communication protocol for the maximum matching problem, significantly simplifying the (3/2)-approximation protocol of Goel, Kapralov, and Khanna (SODA 2012) and extending it from bipartite graphs to general graphs. ⁃ An almost (3/2)-approximation algorithm for the stochastic matching problem, improving upon and significantly simplifying the previous 1.999-approximation algorithm of Assadi, Khanna, and Li (EC 2017). ⁃ An almost (3/2)-approximation algorithm for the fault-tolerant matching problem, which, to our knowledge, is the first non-trivial algorithm for this problem. Our matching sparsifier is obtained by proving new properties of the edge-degree constrained subgraph (EDCS) of Bernstein and Stein (ICALP 2015; SODA 2016) – designed in the context of maintaining matchings in dynamic graphs – that identifies EDCS as an excellent choice for a matching sparsifier. This leads to surprisingly simple and non-technical proofs of the above results in a unified way. Along the way, we also provide a much simpler proof of the fact that an EDCS is guaranteed to contain a large matching, which may be of independent interest.
AB - In this paper, we present a construction of a “matching sparsifier”, that is, a sparse subgraph of the given graph that preserves large matchings approximately and is robust to modifications of the graph. We use this matching sparsifier to obtain several new algorithmic results for the maximum matching problem: ⁃ An almost (3/2)-approximation one-way communication protocol for the maximum matching problem, significantly simplifying the (3/2)-approximation protocol of Goel, Kapralov, and Khanna (SODA 2012) and extending it from bipartite graphs to general graphs. ⁃ An almost (3/2)-approximation algorithm for the stochastic matching problem, improving upon and significantly simplifying the previous 1.999-approximation algorithm of Assadi, Khanna, and Li (EC 2017). ⁃ An almost (3/2)-approximation algorithm for the fault-tolerant matching problem, which, to our knowledge, is the first non-trivial algorithm for this problem. Our matching sparsifier is obtained by proving new properties of the edge-degree constrained subgraph (EDCS) of Bernstein and Stein (ICALP 2015; SODA 2016) – designed in the context of maintaining matchings in dynamic graphs – that identifies EDCS as an excellent choice for a matching sparsifier. This leads to surprisingly simple and non-technical proofs of the above results in a unified way. Along the way, we also provide a much simpler proof of the fact that an EDCS is guaranteed to contain a large matching, which may be of independent interest.
KW - Fault-tolerant matching
KW - Matching sparsifiers
KW - Maximum matching
KW - One-way communication complexity
KW - Stochastic matching
UR - http://www.scopus.com/inward/record.url?scp=85073874299&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85073874299&partnerID=8YFLogxK
U2 - 10.4230/OASIcs.SOSA.2019.11
DO - 10.4230/OASIcs.SOSA.2019.11
M3 - Conference contribution
AN - SCOPUS:85073874299
T3 - OpenAccess Series in Informatics
BT - 2nd Symposium on Simplicity in Algorithms, SOSA 2019 - Co-located with the 30th ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
A2 - Fineman, Jeremy T.
A2 - Mitzenmacher, Michael
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 2nd Symposium on Simplicity in Algorithms, SOSA 2019
Y2 - 8 January 2019 through 9 January 2019
ER -