When to Identify Is to Control: On the Controllability of Combinatorial Optimization ProblemsOberseminar Discrete Optimization

by Jannik Matuschke (KU Leuven)

Monday Jul 6, 2026, 6:15 PM → 7:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

Consider a finite ground set E, a set of solutions X in R^E and a class of objective functions C on X. We are interested in subsets S of E that can control X in the sense that we can induce any given solution x in X as an optimum for any given objective function c in C by adding linear terms to c on the coordinates corresponding to S. We observe that if X is either a convex set or consists of binary vectors, then a set S controls X if and only if it enables us to identify any given solution by its coordinates on S. For the case that X is convex, we moreover show that the sets controlling X induce a matroid. As a consequence, min-weight controlling sets can be computed efficiently from a representation of the affine hull of X in this case.

While the aforementioned result extends to the case where X is the set of bases of a matroid, other natural discrete structures are much less tractable: In particular, when X is the set of s-t-paths in a directed graph, deciding whether an identifying set of a certain cardinality exists is Sigma-2-P-complete. The problem remains NP-hard even when the underlying graph is acyclic, but we derive an approximation for this case by establishing a tight bound on the gap between the size identifying sets for X and the size of identifying sets for its convex hull.

This is joint work with Max Klimm.

 

The Oberseminar takes place in the Seminarraum, 1st floor. Participants are invited to have coffee or tea in the lounge before.