An Investigation of the Recoverable Robust Assignment Problem

Dennis Fischer, Tim A. Hartmann, Stefan Lendl, Gerhard J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


We investigate the so-called recoverable robust assignment problem on complete bipartite graphs, a mainstream problem in robust optimization: For two given linear cost functions c1 and c2 on the edges and a given integer k, the goal is to find two perfect matchings M1 and M2 that minimize the objective value c1(M1) + c2(M2), subject to the constraint that M1 and M2 have at least k edges in common. We derive a variety of results on this problem. First, we show that the problem is W[1]-hard with respect to parameter k, and also with respect to the complementary parameter k = n/2 − k. This hardness result holds even in the highly restricted special case where both cost functions c1 and c2 only take the values 0 and 1. (On the other hand, containment of the problem in XP is straightforward to see.) Next, as a positive result we construct a polynomial time algorithm for the special case where one cost function is Monge, whereas the other one is Anti-Monge. Finally, we study the variant where matching M1 is frozen, and where the optimization goal is to compute the best corresponding matching M2. This problem variant is known to be contained in the randomized parallel complexity class RNC 21, and we show that it is at least as hard as the infamous problem Exact Red-Blue Matching in Bipartite Graphs whose computational complexity is a long-standing open problem.

Original languageEnglish
Title of host publication16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
EditorsPetr A. Golovach, Meirav Zehavi
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)978-3-95977-216-7
Publication statusPublished - 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


  • Assignment problem
  • Exact matching
  • Fixed paramter tractablity
  • Matchings
  • RNC
  • Robust optimization

ASJC Scopus subject areas

  • Software

Cite this