Source-linked AI summary
Constrained Sparsest Input Selection for Structural Controllability is NP-Hard
Yuan Zhang, Jintao Zhang, Yun Feng
TL;DR
The paper addresses the unresolved complexity of selecting the fewest admissible input links for structural controllability, an objective distinct from minimizing input channels. It reduces perfect three-dimensional matching to the decision problem, proving NP-completeness and NP-hardness, and a refinement establishes APX-hardness.
Problem
The complexity of minimizing individual admissible input links in general prescribed patterns remained open, despite polynomial algorithms for restricted cases and the failure of total unimodularity beyond a stated condition.
Source: §1 · pp. 1–2Method
A polynomial-time reduction from perfect three-dimensional matching establishes complexity results for constrained sparsest input-link selection.
Source: §1 · p. 2Results
Takeaways & Limitations
General nondedicated link selection has a genuine complexity boundary from tractable dedicated, restricted-TU, or grouped-input cases.
Source: §7 · p. 5The reduction preprocesses away 3DM instances containing an element in no triple, since those instances are trivially negative.
Source: §3.1 · p. 2
Abstract
from arXiv · showhide
We study the problem of selecting the fewest admissible input--state links that make a structured linear system structurally controllable. This objective counts nonzero entries from prescribed positions of the input matrix and is different from minimizing its number of nonzero columns. Prior work gives polynomial-time algorithms for several restricted cases, including single or dedicated inputs and prescribed input patterns satisfying additional graph-theoretic conditions. We give a polynomial-time reduction from perfect three-dimensional matching, establishing for the first time that the decision problem is NP-complete and the optimization problem is NP-hard. A refinement of the reduction yields an exact optimum relation and shows that the problem is APX-hard. An example also exhibits a strict integrality gap for the natural linear programming relaxation.
1. Introduction
The paper distinguishes entrywise input-link selection from selecting input channels, a distinction that leaves the general constrained problem’s complexity unresolved by prior restricted-case results. A reduction from perfect three-dimensional matching establishes NP-completeness and NP-hardness, while a refinement proves APX-hardness.
1. Introduction
- Prior work provides polynomial algorithms for single-input, dedicated-input, and other restricted entrywise or column-selection cases, but not arbitrary nondedicated patterns.Existing approximation results for broader link-insertion problems do not settle the exact complexity of this problem.Source: §1 · p. 1
- Entrywise selection counts each admissible input link independently, unlike channel selection, and the objectives coincide only for dedicated inputs.Links sharing an input vertex couple their participation in the matching required for structural controllability.Source: §1 · p. 1
- Zhang et al. (2024) established total unimodularity and exact LP relaxation under a grouped-input condition, but TU can fail without it and general link-selection complexity remained open.This paper resolves that open question for the cardinality objective.Source: §1 · pp. 1–2
- A polynomial-time reduction from perfect three-dimensional matching proves NP-completeness of the decision problem and NP-hardness of optimization; a refinement establishes APX-hardness.The general problem has no PTAS unless P = NP.Source: §1 · p. 2
2. Preliminaries and Problem Formulation
The preliminaries define structured systems and the graph criterion for structural controllability, then formulate the task as minimizing retained input links subject to that criterion. The decision version asks whether a feasible selection exists within a given cardinality bound.
2.1. Structured systems
- In the continuous-time system, structured matrices specify the allowed zero and free entries; structural controllability holds when some realization is controllable, which implies almost every admissible realization is.The state and input vectors are x(t) and u(t), and their numerical matrices are eA and eB.Source: §2.1 · p. 2
2.2. Graph terminology and structural controllability
- A digraph consists of vertices and directed edges; strongly connected components are maximal strongly connected subgraphs, and source SCCs have no incoming edge from another SCC.Source: §2.2 · p. 2
- The system digraph combines state-to-state edges from A with input-to-state links from B; all states are input-reachable exactly when every source SCC receives an input link.Source: §2.2 · p. 2
- The system bipartite graph has left and right state copies plus input vertices, and an XL-saturating matching matches every left state vertex.Source: §2.2 · p. 2
- Structural controllability is equivalent to every source SCC receiving an input link and the system bipartite graph having an XL-saturating matching.Source: §2.2 · p. 2
2.3. Constrained sparsest input-link selection
- The feasible input matrices retain any subset of available links, and the objective charges one unit for each nonzero entry, even when multiple links share a column.Source: §2.3 · p. 2
- P1-DEC asks whether a structurally controllable retained-link set of size at most K exists; the paper aims to prove this decision problem NP-complete and P1 NP-hard.Source: §2.3 · p. 2
3. Source Problem and Reduction Construction
The reduction encodes perfect three-dimensional matching (3DM) using source cycles, input links, and downstream states. Its polynomial-size construction is structurally controllable with all available links, and an example illustrates the encoding.
3.1. Perfect three-dimensional matching
- A perfect 3DM selects q triples covering each element of the three sets exactly once, and the construction groups triples by their third coordinate.Each group becomes a directed cycle; each triple also determines an input link and a downstream state connection.Source: §3.1 · p. 2, §3.2 · p. 2
3.2. Construction of the structured system
- The constructed digraph has exactly q source SCCs, one cycle Cc for each c, while each downstream state wb is a singleton SCC that is not a source.Triple-linked cycle states point to downstream states; reserve input links connect separate reserve inputs to those downstream states.Source: §3.2 · p. 3
- The construction is polynomial-time, and its full-availability system is structurally controllable.Cycle edges match the N cycle-state vertices, while q reserve links match the downstream states, giving a matching of size N + q.Source: §3.2 · p. 3
3.3. An Illustration of the construction
- In the q = 2 illustration, three triples yield two source cycles and two downstream states, but no perfect 3DM exists.Figure 1 encodes c by source SCCs, a by input vertices, and b by downstream states; the example also distinguishes cycle, downstream, and input edges by color.Source: §3.3 · p. 3, Figure 1 · p. 3
4. Correctness of the Reduction
The reduction is correct in both directions: a perfect 3DM yields a structurally controllable selection of q links, and any feasible selection within that budget recovers a perfect 3DM.
4.1. Perfect 3DM implies budget feasibility
- A perfect 3DM yields a structurally controllable selection of exactly q input links, one for each third-coordinate cycle.Distinct first and second coordinates ensure the selected links can support a matching that saturates all left state vertices.Source: §4.1 · pp. 3–4
4.2. Budget feasibility implies perfect 3DM
- Any structurally controllable selection of at most q links has exactly one link entering each source SCC, and those links encode a perfect 3DM.The saturating matching forces each selected link to release a cycle predecessor whose downstream edge represents the corresponding triple; matching constraints enforce distinct coordinates.Source: §4.2 · p. 4
5. NP-Completeness and Complexity Consequences
A polynomial-time reduction from 3DM establishes NP-completeness of P1-DEC and NP-hardness of P1. The paper also exhibits a strict integrality gap for the natural LP relaxation on a five-state instance.
5. NP-Completeness and Complexity Consequences
- P1-DEC is NP-complete for general prescribed input-link patterns, so the optimization problem P1 is NP-hard.The reduction establishes NP-hardness, and polynomial-time verification of the certificate and structural controllability establishes membership in NP.Source: §5 · p. 4
- The natural LP relaxation has a strict integrality gap on the five-state instance, and its LP-based method may fail outside the source-SCC grouped input constraint.The constraint is that each input node cannot link to more than one source SCC.Source: §5 · pp. 4–5
6. Approximability
The reduction preserves an exact relation between the constructed input-link optimum and the maximum 3DM size, and its refinement establishes APX-hardness. Consequently, no PTAS exists unless P = NP.
6. Approximability
- APX-hardness does not rule out a fixed-factor algorithm: the passage gives a 2-approximation example, while stating that, unless P = NP, an APX-hard problem has no PTAS.A PTAS gives a (1 + ε)-approximation for every fixed ε > 0 in time polynomial in the input size.Source: §6 · p. 5
- OPT(P1) = 2q − ν(T), where ν(T) is the maximum cardinality of a 3DM contained in T.The construction gives a feasible selection of this size from a maximum matching, and the converse argument establishes the matching lower bound.Source: §6 · p. 5
- Any feasible input-link selection of size s yields in polynomial time a 3DM of size at least 2q − s.This recovery bound is part of the exact relation proved for the reduction.Source: §6 · p. 5
- The problem is APX-hard, even when the full available system is structurally controllable, and has no PTAS unless P = NP.The reduction is an L-reduction from bounded-occurrence maximum 3DM.Source: §6 · p. 5
7. Conclusions and Scope
The results establish NP-hardness for general constrained input-link selection, while distinguishing it from previously tractable structured subclasses.
7. Conclusions and Scope
- General constrained input-link selection is NP-hard, whereas dedicated, restricted-TU, and grouped-input cases remain tractable subclasses.The exact relation also transfers bounded-occurrence maximum 3DM hardness, ruling out a PTAS unless P = NP.Source: §7 · p. 5