2026-07-25T12:07:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15402 2024-03-06T10:55:40Z ddc:004 open_access

An Investigation of the Recoverable Robust Assignment Problem Fischer, Dennis Hartmann, Tim A. Lendl, Stefan Woeginger, Gerhard J. assignment problem matchings exact matching robust optimization fixed paramter tractablity RNC 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 c₁ and c₂ on the edges and a given integer k, the goal is to find two perfect matchings M₁ and M₂ that minimize the objective value c₁(M₁)+c₂(M₂), subject to the constraint that M₁ and M₂ 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 c₁ and c₂ 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 M₁ is frozen, and where the optimization goal is to compute the best corresponding matching M₂. This problem variant is known to be contained in the randomized parallel complexity class RNC², 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dennis Fischer and Tim A. Hartmann and Stefan Lendl and Gerhard J. Woeginger 2021 Is Part Of LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2021.19 urn:nbn:de:0030-drops-154025 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.19 eng https://creativecommons.org/licenses/by/4.0/legalcode