Computational Complexity of Structural Input and Feedback Selection

22 concepts13 papers

Imagine you are designing the control system for a massive infrastructure network—such as a power grid, a fleet of autonomous drones, or a complex metabolic pathway. You cannot afford to place an actuator or a sensor on every single node, nor can you establish communication links between every pair of components. Instead, you face a budget constraint: you must select the minimum cost or minimum number of inputs, outputs, and feedback loops such that the entire system remains controllable, stable, or resilient.

This is the core of the input-output and feedback selection problem in structural control theory. While classical control theory gives us elegant tools to check if a system is controllable once the inputs are fixed, deciding where to place those inputs to optimize cost or sparsity turns out to be a computational minefield. As Parikshit Shah noted in $\mathcal{H}_{2}$-Optimal Decentralized Control Over Posets: A State-Space Solution for State-Feedback, designing optimal control strategies for decentralized systems is generally an NP-hard problem, making it computationally prohibitive for large-scale applications.

To make these systems practical, researchers have spent the last two decades mapping out the exact boundary between the selection problems that are computationally impossible and those that can be solved efficiently.

Why Is Input Selection NP-Hard?

To understand why selecting inputs or feedback loops is difficult, we have to look at how continuous control properties map onto discrete network structures. In structural control, we represent a linear system as a directed graph where nodes are states and edges represent physical interactions. A system is structurally controllable if we can find a set of independent paths from the inputs to all state nodes, ensuring that control signals can propagate throughout the entire network without getting trapped or canceling each other out.

When we try to find the cheapest set of inputs to achieve this, we are essentially trying to select a subset of nodes that can "cover" the rest of the graph via valid dynamical pathways. In On the complexity of the constrained input selection problem for structural linear systems, Sérgio Pequito and A. Pedro Aguiar demonstrated that this selection process can be directly mapped from the classic Set Cover problem—a foundational NP-complete problem in computer science. If you have a collection of sets and want to find the smallest sub-collection that contains all elements, you face an exponential explosion of combinations. In control terms, choosing which nodes to actuate to satisfy structural constraints inherits this exact combinatorial hardness.

This hardness isn't just a byproduct of continuous linear dynamics. The same barriers appear across different system paradigms:

The Added Burden of Performance: Pole Placement and Sparsity

The problem becomes even more severe when we move from basic controllability to performance guarantees, such as arbitrary pole placement (which dictates how fast a system responds or dampens oscillations).

Shana Moothedath explored this in Minimum Cost Feedback Selection for Arbitrary Pole Placement in Structured Systems, proving that finding the minimum-cost feedback configuration for pole placement is not only NP-hard but also inapproximable within a constant factor. This means that no polynomial-time algorithm can guarantee a solution within a constant factor of the optimal cost unless $P=NP$. The underlying reason is that pole placement requires satisfying complex algebraic conditions across the system's transfer function, making the discrete selection of feedback edges tightly coupled with global algebraic constraints.

This intractability extends to decentralized and data-driven settings:

Finding Islands of Tractability

Given that the general problem is computationally intractable, how do we actually design large-scale control systems? The breakthrough insights in this field come from identifying specific structural boundaries where the combinatorial explosion collapses into polynomial-time simplicity.

1. Exploiting Graph Topologies

The complexity of path-matching depends heavily on the network's shape. Shana Moothedath demonstrated that if the underlying system can be modeled as a line graph, a hierarchical network, or uses back-edge feedback, the feedback selection problem can be solved exactly in polynomial time (Minimum Cost Feedback Selection in Structured Systems: Hardness and Approximation Algorithm). In these structured topologies, the paths do not intertwine in complex ways, allowing dynamic programming or greedy strategies to find the global optimum without searching the entire space.

2. Inherent System Properties (Irreducibility and Self-Loops)

Sometimes, the physical nature of the system eliminates bad combinations. Sérgio Daniel Pequito et al. showed in Minimum cost constrained input-output and control configuration co-design problem: A structural systems approach that if the system's dynamic matrix is irreducible (meaning the state graph is strongly connected), the co-design problem can be solved efficiently in polynomial time.

Furthermore, in Analysis and Design of Actuation-Sensing-Communication Interconnection Structures Toward Secured/Resilient LTI Closed-Loop Systems, the authors showed that physical systems with self-loops—which naturally arise when continuous systems are discretized in time—allow the decentralized co-design of sensors and actuators to be solved in polynomial time, even under adversarial conditions. Self-loops ensure that every state has an inherent memory, simplifying the structural conditions required to prevent "fixed modes" that block control signals.

3. Linear Programming Relaxations via Unimodularity

One of the most powerful tools for turning discrete problems into continuous ones is total unimodularity. If a matrix has the property that every square submatrix has a determinant of 0, 1, or -1, then solving a linear program (LP) over that matrix is guaranteed to yield integer solutions.

Yuan Zhang et al. leveraged this in On polynomially solvable constrained input selections for fixed and switched linear structured systems by introducing the "source-SCC separated input" (SSSI) constraint. Under this structural constraint, the minimum-cost input selection problem can be formulated as an LP that naturally outputs exact, discrete input configurations in polynomial time, bypassing the need for combinatorial search.

[General Selection Problem] ---> NP-Hard (Set Cover Reduction)
         |
         +---> Apply SSSI Constraints / Unimodularity ---> [Linear Program] (Polynomial Time)
         |
         +---> Restrict to Line Graphs / Irreducible Matrices ---> [Exact Greedy/DP] (Polynomial Time)

4. Approximation and Decoupling

When exact solutions are impossible, we can bound the error. In Approximating constrained minimum cost input-output selection for generic arbitrary pole placement in structured systems, Shana Moothedath developed an approximation algorithm that breaks the joint input-output selection problem into three decoupled sub-problems, achieving an order-optimal approximation ratio.

Similarly, Alex Olshevsky provided an efficient $O(n + m\sqrt{n})$ algorithm in Minimum input selection for structural controllability for finding the minimum number of inputs for standard structural controllability, even with forbidden states. This demonstrates that careful algorithmic design can bypass hardness for specific variants of the problem, even when related problems (like strong structural controllability) remain strictly NP-hard.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_np_hard_input_selection_fd00b6f2,
  title = {NP-hard input selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/np-hard-input-selection/rdr_fd00b6f2025d47dbabb0f2651cae354b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_np_hard_input_selection_fd00b6f2_v1,
  title = {NP-hard input selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/np-hard-input-selection/rdr_fd00b6f2025d47dbabb0f2651cae354b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake