Restricted Matchings and Edge Colorings

• Applicant: Professor Dr. Dieter Rautenbach
• Subject Area: Theoretical Computer Science ; Mathematics
• Term: from 2018 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 388217545

• Final Report Year: 2021

Final Report Abstract

In this project we investigated restricted matchings in graphs such as induced matchings, uniquely restricted matchings, and acyclic matchings. While the algorithmic problems related to general matchings are among the most famous efficiently solvable problems in discrete optimization, the corresponding problems for the mentioned restricted types of matchings are all hard. We managed to discover several beautiful results concerning the equality of different matching parameters and several tight lower bounds on the respective maximum sizes of the different matchings. Apart from these more structural results, we also provide efficient algorithms for restricted graph classes and several involved approximation algorithms.

Publications

• Uniquely restricted matchings in subcubic graphs without short cycles, J. Graph Theory
  M. Fürst and D. Rautenbach
  (See online at https://doi.org/10.1002/jgt.22632)
• Approximating Maximum Uniquely Restricted Matchings in Bipartite Graphs, Discrete Appl. Math. 267 (2019), 30-40
  J. Baste, D. Rautenbach, and I. Sau
  (See online at https://doi.org/10.1016/j.dam.2019.04.024)
• Lower bounds on the uniquely restricted matching number, Graphs Combin. 35 (2019), 353-361
  M. Fürst and D. Rautenbach
  (See online at https://doi.org/10.1007/s00373-018-1991-8)
• On some hard and some tractable cases of the maximum acyclic matching problem, Ann. Oper. Res. 279 (2019), 291-300
  M. Fürst and D. Rautenbach
  (See online at https://doi.org/10.1007/s10479-019-03311-1)
• Uniquely restricted matchings in subcubic graphs, Discrete Appl. Math. 262 (2019), 189-194
  M. Fürst. M.A. Henning, and D. Rautenbach
  (See online at https://doi.org/10.1016/j.dam.2019.02.013)
• Approximating Maximum Acyclic Matchings by Greedy and Local Search Strategies, 26th International Conference on Computing and Combinatorics (COCOON 2020), Atlanta, USA, August 2020, Lecture Notes in Computer Science 12273 (2020), 542-553
  J. Baste, M. Fürst and D. Rautenbach
  (See online at https://doi.org/10.1007/978-3-030-58150-3_44)
• Low Weight Perfect Matchings, Electron. J. Comb. 2020
  S. Ehard, E. Mohr and D. Rautenbach
  (See online at https://doi.org/10.37236/9994)
• On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs, Theor. Comput. Sci. 804 (2020), 126-138
  M. Fürst and D. Rautenbach
  (See online at https://doi.org/10.1016/j.tcs.2019.11.020)