Secure Maximum Weight Matching Approximation on General Graphs

Workshop on Privacy in the Electronic Society, pp. 83–87

Abstract

Privacy-preserving protocols for matchings on general graphs can be used for applications such as online dating, bartering, or kidney donor exchange. In addition, they can act as a building block for more complex protocols. While privacy-preserving protocols for matchings on bipartite graphs are a well-researched topic, the case of general graphs has experienced significantly less attention so far. We address this gap by providing the first privacy-preserving protocol for maximum weight matching on general graphs. To maximize the scalability of our approach, we compute an 1/2-approximation instead of an exact solution. For N nodes, our protocol requires O(N log N) rounds, O(N^3) communication, and runs in only 12.5 minutes for N=400.

Authors 5

1. Andreas Brüggemann

   Technische Universität Darmstadt

   Affiliation as printed

   Technical University of Darmstadt, Darmstadt, Germany

2. Malte Breuer Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

3. Andreas Klinger Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

4. Thomas H. Schneider

   Technische Universität Darmstadt

   Affiliation as printed

   Technical University of Darmstadt, Darmstadt, Germany

5. Ulrike Meyer Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany