Complexity of the Directed Robust b‐Matching Problem and Its Variants on Different Graph Classes

Networks

Abstract

ABSTRACT The ‐matching problem is a well‐known generalization of the classical matching problem with various applications in operations research and computer science. Given an undirected graph, each vertex has a capacity , indicating the maximum number of times it can be matched, while edges can also be used multiple times. The problem is solvable in polynomial time and has many real‐world applications. In some of them, a feasible matching must exactly satisfy the capacities , leading to the so‐called perfect ‐matching problem. Typically, the capacities are assumed to be fixed and known. However, in practice, these capacities often face uncertainties, such as worker availability or customer demand fluctuations. This article analyses a robust variant of both the ‐matching and perfect ‐matching problems, accounting for such capacity uncertainties, termed the Directed Robust ‐Matching Problem (DRU). We study the computational complexity of this problem across different classes of graphs, providing insights into its tractability for potential applications.

Authors 2

1. Jenny Segschneider Aachen Teaching and Research Area Discrete Optimization

   RWTH Aachen University

   Affiliation as printed

   Teaching and Research Area Discrete Optimization RWTH Aachen University Aachen North Rhine‐Westphalia Germany

2. Arie M. C. A. Koster Aachen Teaching and Research Area Discrete Optimization

   RWTH Aachen University

   Affiliation as printed

   Teaching and Research Area Discrete Optimization RWTH Aachen University Aachen North Rhine‐Westphalia Germany