The computational complexity of weighted greedy matching

Deligkas, A.; Mertzios, G.B.; Spirakis, P.G.

Abstract

Motivated by the fact that in several cases a matching in a graph is stable if and only if it is produced by a greedy algorithm, we study the problem of computing a maximum weight greedy matching on weighted graphs, termed GREEDYMATCHING. In wide contrast to the maximum weight matching problem, for which many efficient algorithms are known, we prove that GREEDYMATCHING is strongly NP-hard and APX-complete, and thus it does not admit a PTAS unless P=NP, even on graphs with maximum degree at most 3 and with at most three different integer edge weights. Furthermore we prove that GREEDYMATCHING is strongly NP-hard if the input graph is in addition bipartite. Moreover we consider three natural parameters of the problem, for which we establish a sharp threshold behavior between NP-hardness and computational tractability. On the positive side, we present a randomized approximation algorithm (RGMA) for GREEDYMATCHING on a special class of weighted graphs, called bushgraphs. We highlight an unexpected connection between RGMA and the approximation of maximum cardinality matching in unweighted graphs via randomized greedy algorithms. We show that, if the approximation ratio of RGMA is ρ, then for every ε > 0 the randomized MRG algorithm of (Aronson et al. 1995) gives a (ρ − ε)-approximation for the maximum cardinality matching. We conjecture that a tightbound for ρ is 2/3; we prove our conjecture true for four subclasses of bush graphs. Proving a tight bound for the approximation ratio of MRG on unweighted graphs (and thus also proving a tight value for ρ) is a long-standing open problem (Poloczek and Szegedy 2012). This unexpected relation of our RGMA algorithm with the MRG algorithm may provide new insights for solving this problem.

Citation

Deligkas, A., Mertzios, G., & Spirakis, P. (2017, February). The computational complexity of weighted greedy matching. Presented at 31st AAAI Conference on Artificial Intelligence (AAAI-17), San Francisco, California, USA

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 31st AAAI Conference on Artificial Intelligence (AAAI-17)
• Start Date: Feb 4, 2017
• End Date: Feb 9, 2017
• Acceptance Date: Nov 12, 2016
• Online Publication Date: Feb 10, 2017
• Publication Date: Feb 10, 2017
• Deposit Date: Dec 5, 2016
• Publicly Available Date: Dec 6, 2016
• Pages: 466-472
• Series Title: Proceedings of the ... AAAI Conference on Artificial Intelligence
• Series ISSN: 2159-5399,2374-3468
• Book Title: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17) : Hilton, San Francisco, Union Square, February 4, 2017 – February 10.
• Public URL: https://durham-repository.worktribe.com/output/1148451
• Publisher URL: https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14266
• Additional Information: Conference date: 4-9 February 2017