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

Max Klimm, Jannik Matuschke

Abstract

Consider a finite ground set $E$, a set of feasible solutions $X \subseteq \mathbb{R}^{E}$, and a class of objective functions $\mathcal{C}$ defined on $X$. We are interested in subsets $S$ of $E$ that 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 \mathcal{C}$ by adding linear terms to $c$ on the coordinates corresponding to $S$. This problem has many applications, e.g., when $X$ corresponds to the set of all traffic flows, the ability to control implies that one is able to induce all target flows by imposing tolls on the edges in $S$. Our first result shows the equivalence between controllability and identifiability. If $X$ is convex, or if $X$ consists of binary vectors, then $S$ controls $X$ if and only if the restriction of $x$ to $S$ uniquely determines $x$ among all solutions in $X$. In the convex case, we further prove that the family of controlling sets forms a matroid. This structural insight yields an efficient algorithm for computing minimum-weight controlling sets from a description of the affine hull of $X$. While the equivalence extends to matroid base families, the picture changes sharply for other discrete domains. We show that when $X$ is equal to the set of $s$-$t$-paths in a directed graph, deciding whether an identifying set of a given cardinality exists is $Σ\mathsf{_2^P}$-complete. The problem remains $\mathsf{NP}$-hard even on acyclic graphs. For acyclic instances, however, we obtain an approximation guarantee by proving a tight bound on the gap between the smallest identifying sets for $X$ and its convex hull, where the latter corresponds to the $s$-$t$-flow polyhedron.

Introduction

In the management of complex infrastructure—ranging from urban traffic networks to national power grids—the ability to steer a system toward a desired state is paramount. However, full control over every variable is rarely feasible. A central question in optimization theory is: what is the minimum set of control points required to ensure any target state can be made "optimal"?

This paper formalizes this as the Controllability Problem. Given a set of feasible solutions $X$ (e.g., all possible traffic distributions) and a class of cost functions, we seek the smallest subset of variables $S \subseteq E$ such that by adjusting only the costs associated with $S$, any $x \in X$ can be rendered the unique optimal solution. This "bilevel" problem is inherently difficult because verifying a set $S$ requires checking if every possible target state can be incentivized over all other alternatives.

The Equivalence Principle: Identification as Control

A key contribution of this work is establishing a fundamental link between Controllability and Identifiability. A subset $S$ is "identifying" if every distinct solution $x, x' \in X$ differs in at least one coordinate within $S$. Essentially, if you know the values of the variables in $S$, you know the entire solution.

The authors prove that for convex sets and sets of binary vectors, these two concepts are equivalent. If a set of variables is sufficient to distinguish between any two solutions, it is also sufficient to "price" any solution into optimality. This equivalence simplifies the problem significantly in these domains, as identifiability is often easier to reason about than the bilevel optimization required for controllability.

Convex Optimization and Matroid Structures

When the feasible set $X$ is convex (such as the set of all valid network flows), the problem exhibits remarkable structural properties. The authors demonstrate that the family of controlling sets for a convex $X$ forms a matroid.

This is a significant result because matroids allow for the use of greedy algorithms. Consequently, finding the minimum-weight controlling set—where different control points might have different "costs" to implement—can be solved in polynomial time. This efficiency makes the theory highly applicable to continuous systems like flow networks, where one might want to find the cheapest set of edges to toll to control overall traffic flow.

The Discrete Challenge: The Complexity of Paths

The transition from continuous flows to discrete paths reveals a "convexity gap" in computational complexity. While controlling flows is efficient, controlling $s$-$t$ paths in a network is significantly harder.

The researchers show that for general directed graphs, determining if an identifying set of a certain size exists is $\Sigma_2^P$-complete. This places the problem higher in the complexity hierarchy than standard NP-complete problems, suggesting that even verifying a solution is difficult. Even in Directed Acyclic Graphs (DAGs), the problem remains NP-hard, though the authors provide a $\sqrt{|E|}$-approximation guarantee for these cases.

Key Results and Approximations

The paper provides a comprehensive map of the complexity landscape:

  • Convex and Matroid Domains: Minimum-weight controlling sets are computable in polynomial time.
  • Explicit Solution Lists: For cases where $X$ is given as an explicit list of vectors, a $2 \ln |X|$-approximation algorithm is provided.
  • Network Path Hardness: The $\Sigma_2^P$-completeness for general digraphs and NP-hardness for DAGs highlights the intrinsic difficulty of discrete path control compared to continuous flow control.

Conclusion

This research provides a rigorous foundation for understanding how to influence optimization systems through partial control. By proving the equivalence of identifiability and controllability in key domains and identifying the matroid structure of convex controlling sets, the authors offer practical tools for continuous systems. Simultaneously, their complexity results for discrete paths caution against expecting simple solutions in network routing problems, pointing toward the need for robust approximation strategies and specialized graph topologies in future work.

Summary updated

Abstract

Consider a finite ground set $E$, a set of feasible solutions $X \subseteq \mathbb{R}^{E}$, and a class of objective functions $\mathcal{C}$ defined on $X$. We are interested in subsets $S$ of $E$ that 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 \mathcal{C}$ by adding linear terms to $c$ on the coordinates corresponding to $S$. This problem has many applications, e.g., when $X$ corresponds to the set of all traffic flows, the ability to control implies that one is able to induce all target flows by imposing tolls on the edges in $S$. Our first result shows the equivalence between controllability and identifiability. If $X$ is convex, or if $X$ consists of binary vectors, then $S$ controls $X$ if and only if the restriction of $x$ to $S$ uniquely determines $x$ among all solutions in $X$. In the convex case, we further prove that the family of controlling sets forms a matroid. This structural insight yields an efficient algorithm for computing minimum-weight controlling sets from a description of the affine hull of $X$. While the equivalence extends to matroid base families, the picture changes sharply for other discrete domains. We show that when $X$ is equal to the set of $s$-$t$-paths in a directed graph, deciding whether an identifying set of a given cardinality exists is $Σ\mathsf{_2^P}$-complete. The problem remains $\mathsf{NP}$-hard even on acyclic graphs. For acyclic instances, however, we obtain an approximation guarantee by proving a tight bound on the gap between the smallest identifying sets for $X$ and its convex hull, where the latter corresponds to the $s$-$t$-flow polyhedron.
BibTeX
@misc{klimm2026when,
  author = {Max Klimm and Jannik Matuschke},
  title = {{When to Identify Is to Control: On the Controllability of Combinatorial Optimization Problems}},
  year = {2026},
  eprint = {2602.16311},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.16311},
}

Loading related content...

Figure