Open Research Index

Complexity of partitioned-items response problems: matchings and perfect matchings

Christoph Buchheim, Lowig Duer, Eva Ley, Maximilian Merkert, Komal Muluk

arXivarxiv/2607.09953Jul 10, 2026math.OCscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2607.09953
curl -X POST /api/v1/records/arxiv/2607.09953/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.09953/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'