The Computational Complexity of Weighted Greedy Matching
Authors: Argyrios Deligkas, George Mertzios, Paul Spirakis
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 bush graphs. 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 tight bound for ρ is 2/3; we prove our conjecture true for four subclasses of bush graphs. |
| Researcher Affiliation | Academia | Argyrios Deligkas Department of Computer Science University of Liverpool, UK. a.deligkas@liverpool.ac.uk George B. Mertzios School of Engineering and Computing Sciences Durham University, UK. george.mertzios@durham.ac.uk Paul G. Spirakis Department of Computer Science University of Liverpool, UK and Computer Technology Institute, Greece. p.spirakis@liverpool.ac.uk |
| Pseudocode | Yes | Algorithm 1: Greedy Matching Procedure, Algorithm 2: RGMA algorithm, Algorithm 3: Bush decomposition |
| Open Source Code | No | The paper does not provide any statements about open-sourcing code or links to repositories. |
| Open Datasets | No | The paper is theoretical and does not describe or use any public datasets for training, validation, or testing. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits (training, validation, test) for experimental reproduction. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |