AI summaryⓘ
The authors study a two-level optimization problem where a leader and follower work together to find solutions to problems involving combinations of items. They focus on cases where the leader wants the follower’s solution to include some must-have items and exclude some forbidden ones. They explore how difficult it is to solve these problems for different item combinations, using examples related to choosing matchings in graphs. They find that even with one required or forbidden item, the problem can be hard, but it becomes manageable when restricted to a limited number of special items. Also, when every item is either mandatory or forbidden, the problem is easier for perfect matchings but remains hard for maximum-weight matchings.
bilevel optimizationcombinatorial optimizationresponse problemmandatory itemsforbidden itemsmaximum-weight matchingminimum-weight perfect matchingfixed-parameter tractableNP-hardpolynomial time
Authors
Christoph Buchheim, Lowig Duer, Eva Ley, Maximilian Merkert, Komal Muluk
Abstract
We consider bilevel optimization problems in which leader and follower jointly construct a feasible solution for an underlying combinatorial optimization problem. Response problems ask whether the leader can encourage -- or, in the pessimistic setting, enforce -- a reaction of the follower that includes a set of mandatory items while excluding a set of forbidden items. Our investigation focuses on tractability results for various cases which emerge from different combinations of the total number of mandatory, forbidden, and neutral items. After providing some results for response problems that hold for any underlying combinatorial optimization problem, we examine response problems over the maximum-weight matching problem and the minimum-weight perfect matching problem as illustrative and surprisingly varied examples. Among other results, we show that the response problem is hard for even a single given mandatory or forbidden edge. On the other hand, it is fixed-parameter tractable with respect to the total number of non-mandatory edges. If, however, each follower's edge is either mandatory or forbidden, the response problem for the perfect matching problem is solvable in polynomial time while it remains NP-hard for the maximum-weight matching problem.