CS Paper Radar

Constrained Sparsest Input Selection for Structural Controllability is NP-Hard

Yuan Zhang, Jintao Zhang, Yun Feng

eess.SY ·submitted 2026-10-22 12:43 UTC · v2

Abstract

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.

Comment
6 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

Verifying Control Invariance of H-Polytopes is coNP-Complete

eess.SY math.OC ·2026-10-27 ·Mario Eduardo Villanueva, Boris Houska
theory similarity 0.59
Abstract

We prove that verifying whether an H-polytope is control invariant for a discrete-time linear system with polytopic input constraints is \textsc{coNP}-complete. This establishes a fundamental computational complexity barrier for set-theoretic control. As an immediate consequence, the exact computation of maximal control invariant subsets of H-polytopes is \textsc{coNP}-hard. These hardness results hold regardless of whether the input constraint set is given in H- or V-representation.

0.28

First-Order Optimization as Minimum-Time Control

eess.SY math.OC ·2026-08-14 ·Liraz Mudrik, Isaac Kaminer, Pramod P. Khargonekar
benchmark similarity 0.58
Abstract · 13 pages, 4 figures

We formulate first-order optimization as a minimum-time control problem. The iterate is the state, the update, a combination of the gradients observed so far, is the control, and the points with gradient norm at most a prescribed tolerance form the target set. For a fixed objective and start, the minimum number of oracle queries needed to reach the target is a value function: it measures the complexity of the instance, not the worst case over a class. On a strongly convex quadratic, the conjugate gradient iterates emerge from the discrete Pontryagin conditions, and the value is a controllability index. Beyond the quadratic, a Hessian-generated reachable span replaces the controllability matrix, and feasibility becomes a reachability question: whether a critical point can be reached at all, and in how many steps, is read from the span. Curvature is a resource: a checkable condition certifies that an instance needs fewer steps than the controllability index of its quadratic model at the minimizer, and the gap can grow without bound with the dimension. The value is thus a benchmark for the intrinsic difficulty of each instance, against which any first-order method can be measured.

0.10

On the Minimal Controllability of Boolean Networks With $k$-Regular Dependency Graphs

eess.SY math.OC ·2026-11-05 ·Christopher H. Fok, Chi-Wing Wong, Wai-Ki Ching
theory similarity 0.54
Abstract · 16 pages

Boolean networks (BNs) are widely used to model gene regulatory networks and other biological systems. In this paper, we investigate the minimal controllability problem for BNs subject to degree constraints. We first establish three new best-case upper bounds for XOR-BNs whose dependency graphs are $k$-regular. We then introduce classes of BNs that are invariant under cyclically partite transformation (CPT-invariant) and prove theorems connecting BN controllability with the surjectivity of vector-valued Boolean functions. Finally, by combining an analysis of this surjectivity with a probabilistic argument, we derive a new general lower bound on the minimum number of control nodes required for majority-type threshold BNs with $(2k+1)$-regular dependency graphs.

0.30

The Complexity of Recognizing SDP Exactness for the Maximum Cut Problem

cs.CC math.OC ·2026-09-03 ·Avinash Bhardwaj
similarity 0.52
Abstract

The standard semidefinite programming (SDP) relaxation of Max-Cut is exact when its optimum equals the maximum cut value. Delorme and Poljak resolved NP-completeness of recognizing exactness for weighted graphs and left the unweighted case open. We show that recognition is NP-complete even for connected simple unweighted graphs, and hence strongly NP-complete for nonnegative integer edge weights. The reduction provides an explicit SDP optimum and makes the additive integrality gap equal to the minimum number of unsatisfied clauses in the source formula. Recognition remains NP-complete even when an exact rational optimal primal--dual pair is supplied. We also establish strong NP-hardness of recognizing exactness of the Frieze--Jerrum Max-$k$-Cut relaxation for every fixed $k\ge3$, even for connected graphs with nonnegative integer edge weights. An independent bounded-weight construction gives a second proof for Max-Cut. Finally, reductions preserving the additive gap up to explicit factors establish strong NP-completeness of exactness recognition for a basic Max-DiCut SDP and NP-hardness for a Max-Bisection SDP.

0.33

Binary Affine Optimization with Nearly-Graphic Constraint Matrices

cs.DS math.OC ·2026-11-17 ·Qiming Fang, Sihong Shao, Yuxuan Wu
similarity 0.52
Abstract · 25 Pages, 5 Figures

We present a polynomial-time algorithm for binary affine optimization with a linear objective when every column of the constraint matrix has Hamming weight at most 2, and prove that the problem is NP-hard when every column of the constraint matrix has Hamming weight exactly 3. We obtain fixed-parameter tractable (FPT) algorithms for the unrestricted problem provided that a nearly-graphic certificate is given, where the certificate roughly measures how far the constraint matrix is from having columns of Hamming weight at most 2. We apply our FPT algorithm to Max-Lin$_2$ on graphs and obtain FPT algorithms parameterized by the contraction distance and contraction rank of the graph, utilizing the concept of Eulerian-spanning set. In the case of contraction distance, another FPT algorithm can be used to find the corresponding certificate; that is, we obtain an FPT algorithm that requires no information beyond the problem instance itself.

0.41

Optimal input design via Frank-Wolfe

eess.SY math.OC ·2026-09-08 ·Fethi Bencherki, Bruce Lee, Nikolai Matni, Anders Rantzer
similarity 0.52
Abstract · 7 pages, 4 figures

We study optimal input design over a finite horizon for linear dynamical systems. The goal is to minimize a weighted inverse-covariance (information) criterion subject to an energy budget. The set of covariances achievable by causal policies is convex but lacks a tractable explicit description, ruling out projection-based methods. We show that Frank--Wolfe applies naturally: each linear minimization subproblem is a budget-constrained finite-horizon linear quadratic (LQ) problem, solvable by a Riccati recursion and one-dimensional bisection over a Lagrange multiplier. Using smoothness of the objective over the feasible set, we establish an $\mathcal{O}(1/M)$ convergence rate for the objective value, while strong convexity yields an $\mathcal{O}(1/\sqrt{M})$ rate for the iterates. We further extend the framework to input design for system identification with unknown dynamics and adaptive online LQR, and illustrate the approach numerically.

0.28

Hardness of integer linear feasibility with cyclic support

cs.DM math.OC ·2026-11-05 ·Marco Di Summa
theory similarity 0.51
Abstract

We prove that integer linear feasibility is strongly $NP$-complete even when the constraint matrix has exactly two nonzero entries in every row and column, with its support forming a single cycle. This holds already for monotone systems (one positive and one negative coefficient in each inequality) with nonzero coefficients of absolute value $2$ or $3$ and right-hand sides in $\{-1,0,1,2\}$. No variable bounds are supplied separately from the system. For systems in which each inequality involves at most two variables, this strengthens known hardness results by restricting all numerical data to fixed finite sets. For systems in which each variable occurs in at most two inequalities, this establishes, to the best of our knowledge, the first $NP$-hardness result for feasibility. We also give negative answers, unless $P=NP$, to questions on polynomial-time solvability of integer programs with bounded coefficients and bounded totally $Δ$-modular treewidth, and on fixed-parameter tractability of integer bound propagation with respect to coefficient and right-hand-side magnitudes.

0.24

Parameterized Complexity of Spanner Problems with Independent Weights and Lengths

cs.DS ·2026-09-24 ·Marius Bächler, Markus Chimani, Henning Jasper
theory similarity 0.51
Abstract

In this paper, the parameterized complexity of the multiplicative $α$-spanner problem with independent weights and lengths on undirected graphs is considered for the first time. All prior FPT results (except one on DAGs) assume basic instances (i.e., with unit weights and lengths) and are parameterized in the stretch factor $α$ and the (in practice typically non-constant) number of removed edges. We show that several parameterizations do not allow FPT algorithms. However, our exclusion approach generalizes an existing algorithm for basic instances to arbitrary weights and lengths. It is parameterized by the total removed weight and a new tightness parameter. The latter is more precise than $α$ and allows us to also improve the best known result for basic instances. Our second algorithm, called inclusion approach, uses the natural parameterization in the spanner's total weight. We prove that this sole parameter leaves a W[2]-hard problem, but also show FPT algorithms exist when augmented with secondary parameters.

0.26