1

Minimal Reachability is Hard To Approximate

arXiv:1710.10244v3 [] 20 Feb 2018

A. Jadbabaie, A. Olshevsky, G. J. Pappas, V. Tzoumas

Abstract—In this note, we consider the problem of choosing
which nodes of a linear dynamical system should be actuated
so that the state transfer from the system’s initial condition to
a given final state is possible. Assuming a standard complexity
hypothesis, we show that this problem cannot be efficiently solved
or approximated in polynomial, or even quasi-polynomial, time.

x1 (t)

x2 (t)

x3 (t)

x4 (t)

···

xn (t)

I. I NTRODUCTION
During the last decade, researchers in systems, optimization,
and control have focused on questions such as:
• (Actuator Selection) How many nodes do we need to actuate in a gene regulatory network to control it? [1], [2]
• (Input Selection) How many inputs are needed to drive the
nodes of a power system to fully control its dynamics? [3]
• (Leader Selection) Which UAVs do we need to choose in
a multi-UAV system as leaders for the system to complete
a surveillance task despite communication noise? [4], [5]
The effort to answer such questions has resulted in numerous
papers on topics such as actuator placement for controllability [6], [7]; actuator selection and scheduling for bounded
control effort [8]–[11]; resilient actuator placement against
failures and attacks [12], [13]; and sensor selection for target
tracking and optimal Kalman filtering [14]–[17]. In all these
papers the underlying optimization problems have been proven
(i) either polynomially-time solvable [1]–[3] (ii) or NP-hard,
in which case polynomial-time algorithms have been proposed
for their approximate solution [4]–[17].
But in systems, optimization, and control, such as in power
systems [18], [19], transportation networks [20], and neural
circuits [21], [22], the following problem also arises:
Minimal Reachability Problem. Given times t0 and t1 such
that t1 > t0 , vectors x0 and x1 , and a linear dynamical
system with state vector x(t) such that x(t0 ) = x0 , find the
minimal number of system nodes we need to actuate so that
the state transfer from x(t0 ) = x0 to x(t1 ) = x1 is feasible.
For example, the stability of power systems is ensured by
placing a few generators such that the state transfers from a set
of possible initial conditions to the zero state are feasible [19].
The minimal reachability problem relaxes the objectives of
the applications in [1]–[17]. For example, in comparison to the
actuator placement problem for controllability [6], the minimal
A. Jadbabaie is with the Institute for Data, Systems, and Society, Massachusetts Institute of Technology, Cambridge, MA 02139 USA,
jadbabai@mit.edu.
A. Olshevsky is with the Department of Electrical and Computer Engineering and the Division of Systems Engineering, Boston University, Boston, MA
02215 USA, alexols@bu.edu.
G. J. Pappas and V. Tzoumas are with the Department of Electrical and
Computer Engineering, University of Pennsylvania, Philadelphia, PA 19104
USA, pappasg@seas.upenn.edu, vtzoumas@seas.upenn.edu.

Fig. 1.
Graphical representation of the linear system ẋ1 (t) =
P
n
ẋi (t) = 0, i = 2, . . . , n; each node represents an entry
j=2 xj (t),
of the system’s state (x1 (t), x2 (t), . . . , xn (t)), where t represents time; the
edges denote that the evolution in time of x1 depends on (x2 , x3 , . . . , xn ).

reachability problem aims to place a few actuators only to
make a single transfer between two states feasible, whereas the
minimal controllability problem aims to place a few actuators
to make the transfer among any two states feasible [6], [7].
The fact that the minimal reachability problem relaxes the
objectives of the papers [1]–[17] is an important distinction
whenever we are interested in the feasibility of only a few
state transfers by a small number of placed actuators. The
reason is that under the objective of minimal reachability the
number of placed actuators can be much smaller in comparison
to the number of placed actuators under the objective of
controllability. For example, in the system of Fig. 1 the number
of placed actuators under the objective of minimal reachability
from (0, . . . , 0) to (1, . . . , 0) is one, whereas the number of
placed actuators under the objective of controllability grows
linearly with the system’s size.
The minimal reachability problem was introduced in [23],
where it was found to be NP-hard. Similar versions of the
reachability problem were studied in the context of power
systems in [19] and [24]. For the polynomial-time solution of
the reachability problems in [19], [23], [24], greedy approximation algorithms were proposed therein. The approximation
performance of these algorithms was claimed by relying on
the modularity result [25, Lemma 8.1], which states that the
distance from a point to a subspace created by the span of a
set of vectors is supermodular in the choice of the vectors.
In this note, we first show that the modularity result [25,
Lemma 8.1] is incorrect. In particular, we show this via a
counterexample to [25, Lemma 8.1], and as a result, we prove
that the distance from a point to a subspace created by the span
of a set of vectors is non-supermodular in the choice of the
vectors. Then, we also prove the following strong intractability
result for the minimal reachability problem, which is our main
contribution in this paper:
Contribution 1. Assuming NP ∈
/ BPTIME(npoly log n ), we
show that for each δ > 0, there is no polynomial-time

2

algorithm that can distinguish1 between the two cases where:
– the reachability problem has a solution with cardinality k;
– the reachability problem has no solution with cardinality
1−δ
k2Ω(log n), where n is the dimension of the system.
We note that the complexity hypothesis NP
∈
/
BPTIME(npoly log n ) means there is no randomized algorithm
c
which, after running for O(n(log n) ) time for some constant c,
outputs correct solutions to problems in NP with probability
2/3; see [26] for more details.
Notably, Contribution 1 remains true even if we allow the
algorithm to search for an approximate solution that is relaxed
as follows: instead of choosing the actuators to make the
state transfer from the initial state x0 to a given final state x1
possible, some other state x
b1 that satisfies kx1 − x
b1 k22 ≤ ǫ
should be reachable from x0 . This is a substantial relaxation
of the reachability problem’s objective, and yet, we show that
the intractability result of Contribution 1 still holds.
The rest of this note is organized as follows. In Section II, we introduce formally the minimal reachability problem. In Section III, we provide a counterexample to [25,
Lemma 8.1]. In Section IV, we present Contribution 1; in Section V, we prove it. Section VI concludes the paper.
II. M INIMAL R EACHABILITY P ROBLEM
In this section we formalize the minimal reachability problem. We start by introducing the systems considered in this
paper and the notions of system node and of actuated node set.
System. We consider linear systems of the form
ẋ(t) = Ax(t) + Bu(t),

t ≥ t0 ,

(1)

where t0 is a given starting time, x(t)∈ Rn is the system’s
state at time t, and u(t)∈ Rm is the system’s input vector. ◭
In this paper, we want to actuate the minimal number of
the nodes of the system in eq. (1) to make a desired statetransfer feasible (not achieving necessarily controllability). We
formalize this objective using the following two definitions.
Definition 1 (System node). Given a system as in eq. (1),
where x(t) ∈ Rn, we let x1 (t), x2 (t), . . . , xn (t) ∈ R be the
components of x(t), i.e., x(t) = (x1 (t), x2 (t), . . . , xn (t)).
We refer to each xi (t) as a system node.
◭
Definition 2 (Actuated node set). Given a system as in eq. (1),
we say that the set S ⊆ {1, 2, . . . , n} is an actuated node set
if the system dynamics can be written as
ẋ(t) = Ax(t) + I(S)Bu(t),

t ≥ t0 ,

(2)

where I(S) is a diagonal matrix such that if i ∈ S, the i-th
entry of I(S)’s diagonal is 1, otherwise it is 0.
◭
The definition of I(S) in eq. (2) implies that the input u(t)
affects only the system nodes xi (t) where i ∈ S.
1 We say that an algorithm can distinguish between two (disjoint) cases
A and B if, when fed with an input that is guaranteed to be in either A
or B, the algorithm is able to determine which of the two is the case (e.g.,
by outputing 1 if the input belongs A, and 0 if it belongs to B).

Problem 1 (Minimal Reachability). Given
• times t0 and t1 such that t1 > t0 ,
n
• vectors x0 , x1 ∈ R , and
• a system ẋ(t) = Ax(t) + Bu(t), t ≥ t0 , as in eq. (1),
with initial condition x(t0 ) = x0 ,
find an actuated node set with minimal cardinality such that
there exists an input u(t) defined over the time interval (t0 , t1 )
that achieves x(t1 ) = x1 . Formally, using the notation |S| to
denote the cardinality of a set S:
minimize
S⊆{1,2,...,n}

|S|

such that there exist u : (t0 , t1 ) 7→ Rm, x : (t0 , t1 ) 7→ Rn with
ẋ(t) = Ax(t) + I(S)Bu(t),
x(t0 ) = x0 ,
x(t1 ) = x1 .

t ≥ t0 ,

A special case of interest is when B is the identity matrix.
Then minimal reachability asks for the fewest system nodes to
be actuated directly so that at time t1 the state x1 is reachable
from the system’s initial condition x(t0 ) = x0 .
III. N ON - SUPERMODULARITY

OF DISTANCE FROM POINT
TO SUBSPACE

In this section, we provide a counterexample to the supermodularity result [25, Lemma 8.1]. We begin with some
notation. In particular, given a matrix M ∈ Rn×n, a vector
v ∈ Rn, and a set S ⊂ {1, . . . , n}, let M (S) denote the
matrix obtained by throwing away columns of M not in S.
In addition, for any set S ⊂ {1, . . . , n}, we define the set
function
f (S) = dist2 (v, Range(M (S))),
where dist(y, X) is the distance from a point to a subspace:
dist(y, X) = min ||y − x||2 .
x∈X

We show there exist a vector v and a matrix M such that
the function f : {1, 2, . . . , n} 7→ dist2 (v, Range(M (S))) is
non-supermodular. We start by defining the monotonicity and
supermodularity of set functions.
Definition 3 (Monotonicity). Consider any finite set V. The
set function f : 2V 7→ R is non-decreasing if and only if for
any A ⊆ A′ ⊆ V, we have f (A) ≤ f (A′ ).
◭

In words, a set function f : 2V 7→ R is non-decreasing if
and only if by adding elements in any set A ⊆ V we cannot
decrease the value of f (A).

Definition 4 (Supermodularity [27, Proposition 2.1]). Consider any finite set V. The set function f : 2V 7→ R is
supermodular if and only if for any A ⊆ A′ ⊆ V and x ∈ V,
f (A) − f (A ∪ {x}) ≥ f (A′ ) − f (A′ ∪ {x}).

◭

In words, a set function f : 2V 7→ R is supermodular if and
only if it satisfies the following diminishing returns property:
for any element x ∈ V, the marginal decrease f (A) − f (A ∪
{x}) diminishes as the set A grows; equivalently, for any A ⊆
V and x ∈ V, f (A) − f (A ∪ {x}) is non-increasing.

3

Example 1. We show that for



−1
1
v =  1 ,
M = 1
1
0



0 1
1 0 ,
0 1

the set function f : 2{1,2,3} 7→ dist2 (v, Range(M (S))) is
non-supermodular. In particular, since the vector v is orthogonal to the first and third columns of M ,
f ({1}) = dist2 (v, M ({1})) =
2

f ({1, 3}) = dist (v, M ({1, 3})) =

||v||22

||v||22

Therefore,
f ({1}) − f ({1, 3}) = 0.
At the same time, the span of the first two columns of M is
the subspace {x ∈ R3 : x3 = 0}. Thus,
f ({1, 2}) = dist2 (v, M ({1, 2})) = 1.

Also, since the three columns of M are linearly independent,
f ({1, 2, 3}) = dist2 (v, M ({1, 2, 3})) = 0,
and as a result,
f ({1, 2}) − f ({1, 2, 3}) = 1.
In sum,
f ({1, 2}) − f ({1, 2, 3}) > f ({1}) − f ({1, 3});
hence, for the vector v and matrix M in this example, f :
2{1,2,3} 7→ dist2 (v, Range(M (S))) is non-supermodular. ◭
We remark that the same argument as in Example 1 shows
that the set function g : {1, 2, . . . , n} 7→ R such that g(S) =
[dist(v, Range(M (S))]c is not supermodular for any c > 0.
IV. I NAPPROXIMABILITY OF M INIMAL R EACHABILITY
P ROBLEM
We show that, subject to a widely believed conjecture in
complexity theory, there is no efficient algorithm that solves,
even approximately, Problem 1. Towards the statement of this
result, we next introduce a definition of approximability and
the definition of quasi-polynomial running time.
Definition 5 (Approximability). Consider the minimal reachability Problem 1, and let the set S ⋆ to denote one of its
optimal solutions. We say that an algorithm renders Problem 1
(∆1 (n), ∆2 (n))-approximable if it returns a set S such that:
• there is a state x
b1 such that there is an input u(t) such that
at time t1 we have x(t1 ) = x
b1 and ||b
x1 − x1 k2 ≤ ∆1 (n);
⋆
• the cardinality of the set S is at most ∆2 (n)|S |.
◭

Hence, the definition of (∆1 (n), ∆2 (n))-approximability
allows some slack both in the quality of the reachability
requirement (first point in the itemization in Definition 5), and
in the number of actuators utilized to achieve it (second point
in the itemization in Definition 5).
We introduce next the definition of quasi-polynomial algorithms, using the following big O notation.

Definition 6 (Big O notation). Let N be the set of natural
numbers, and consider two functions h : N 7→ R and g : N 7→
R that take only non-negative values. The big O notation in
the equality h(n) = O(g(n)) means there exists some constant
c > 0 such that for all large enough n, it is h(n) ≤ cg(n). ◭
Definition 6, given a non-negative function g, implies that
O(g(n)) denotes the collection of non-negative functions h
that are bounded asymptotically by g, up to a constant factor.
Definition 7 (Quasi-polynomial running time). An algorithm
c
is quasi-polynomial if it runs in 2O[(log n) ] time, where c is a
constant.
◭
We note that any polynomial-time algorithm is a quasipolynomial time algorithm since nk = 2k log n. At the same
time, a quasi-polynomial algorithm is asymptotically faster
than an exponential-time algorithm, since exponential-time
ǫ
algorithms run in O(2n ) time, for some ǫ > 0.
Definition 8 (Big Omega notation). Let N be the set of natural
numbers, and consider the functions h : N 7→ R and g :
N 7→ R that take only non-negative values. The big Omega
notation in the equality h(n) = Ω(g(n)) means that there
exists some constant c > 0 such that for all large enough n,
it is h(n) ≥ cg(n).
◭
Definition 8, given a non-negative g, implies that Ω(g(n))
denotes the collection of non-negative functions h that are
lower bounded asymptotically by g, up to a constant factor.
We present next our main result in this paper.
Theorem 1 (Inapproximability). For each δ ∈ (0, 1), there is
a collection of instances of Problem 1 where:
• the initial condition is x(t0 ) = 0;
⊤
• the final state x1 is of the form [1, 1, . . . , 1, 0, 0, . . . , 0] ;
• the input matrix is B = I, where I is the identity matrix,
along with a polynomial ∆1 (n) and a function ∆2 (n) =
1−δ
2Ω(log n), such that unless NP∈ BPTIME(npoly log n ),
there is no quasi-polynomial algorithm rendering Problem 1
(∆1 (n), ∆2 (n))-approximable.
Theorem 1 says that if NP ∈
/ BPTIME(npoly log n ) there
is no polynomial time algorithm (or quasi-polynomial time
algorithm) that can choose which entries of the system’s x
state to actuate so that x(t1 ) is even approximately close to a
desired state x1 = [1, 1, . . . , 1, 0, 0, . . . , 0]⊤ at time t1 .
To make sense of Theorem 1, first observe that we can
always actuate every entry of the system’s state, i.e., we can
choose S = {1, 2, . . . , n}. This means every system is (0, n)approximable; let us rephrase this by saying that every system
is (0, 2log n ) approximate. Theorem 1 tells us that we cannot
1−δ
achieve (0, 2O(log n) )-approximability for any δ > 0. In
other words, improving the guarantee of the strategy that
actuates every state by just a little bit, in the sense of replacing
δ = 0 with some δ > 0, is not possible —subject to the
complexity-theoretic hypothesis NP ∈
/ BPTIME(npoly log n ).
Furthermore, the theorem tells us it remains impossible even
if we allow ourselves some error ∆(n) in the target state, i.e.,
1−δ
even (∆(n), 2O(log n) )–approximability is ruled out.

4

Remark 1. In [23, Theorem 3] it is claimed that for any

ǫ > 0 the minimal reachability Problem 1 is ǫ, O log nǫ approximable, which contradicts Theorem 1. However, the
proof of this claim was based on [25, Lemma 8.1], which
we proved incorrect in Section III.
◭

to pick y ∈ Rl that is an optimal solution to the following
optimization problem.

Remark 2. The minimal controllability problem [6] seeks
to place the fewest number of actuators to make the system
controllable. Theorem 1 is arguably surprising, as it was shown
in [6] that the sparsest set of actuators for controllability
can be approximated to a multiplicative factor of O(log n)
in polynomial time. By contrast, we showed in this note that
an almost exponentially worse approximation ratio cannot be
achieved for minimum reachability.
◭

where ||y||0 refers to the number of non-zero entries of y.

V. P ROOF

OF I NAPPROXIMABILITY OF

M INIMAL

R EACHABILITY
We next provide a proof of our main result, namely Theorem 1. We use some standard notation throughout: 1k is the
all-ones vector in Rk , 0k is the zero vector in Rk , and ek is
the k’th standard basis vector. We begin with some standard
definitions related to the reachability space of a linear system.
A. Reachability Space for continuous-time linear systems
Definition 9 (Reachability space). Consider a system ẋ(t) =
Ax(t) + Bu(t) as in eq. (1) whose size is n. The
Range([B, AB, A2 B, . . . , An−1 B]) is called the reachability space of ẋ(t) = Ax(t) + Bu(t).
◭
The reason why Definition 9 is called the reachability space
is explained in the following proposition.
Proposition 1 ([28, Proof of Theorem 6.1]). Consider a system
as in eq. (1), with initial condition x0 . There exists a real
input u(t) defined over the time interval (t0 , t1 ) such that the
solution of ẋ = Ax + Bu, x(t0 ) = x0 satisfies x(t1 ) = x1 if
and only if
x1 − eA(t1 −t0 ) x0 ∈ Range([B, AB, A2 B, . . . , An−1 B]).
The notion of reachability space allows us to redefine the
minimal reachability Problem 1 as follows.
Corollary 1. Problem 1 is equivalent to
minimize |S|

S⊆{1,2,...,n}

such that x1 − eA(t1 −t0 ) x0 ∈

Range([I(S)B, AI(S)B, . . . , An−1 I(S)B]).

Overall, Problem 1 is equivalent to picking
the fewest rows of the input matrix B such that
x1 − eA(t1 −t0 ) x0 is in the linear span of the columns
of [I(S)B, AI(S)B, A2 I(S)B, . . . , An−1 I(S)B].
B. Variable Selection Problem
We show the intractability of the minimum reachability by
reducing it to the variable selection problem, defined next.
Problem 2 (Variable Selection). Let U ∈ Rm×l , z ∈ Rm , and
let ∆ be a positive number. The variable selection problem is

minimize
y∈Rl

such that

kyk0
kU y − zk2 ≤ ∆,

The variable selection Problem 2 is found in [29] to be
inapproximable, even in quasi-polynomial time:
Theorem 2 ([29, Proposition 6]). Unless it is NP∈
BPTIME(npoly log n ), for each δ ∈ (0, 1) there exist:
Ω(log1−δ l)
• a function q1 (l) which is in 2
;
2
• a polynomial p1 (l) which is in O(l);
• a polynomial ∆(l);
• a polynomial m(l),
and a zero-one m(l) × l matrix U such that no quasipolynomial time algorithm can distinguish between the following two cases for large l:
1) There exists a vector y ∈ Rl such that U y = 1m(l) and
||y||0 ≤ p1 (l).
2) For any vector y ∈ Rl such that ||U y − 1m(l) ||22 ≤ ∆(l),
we have ||y||0 ≥ p1 (l)q1 (l).

Informally, unless NP∈BPTIME(npoly log n ), Theorem 2
says that Problem 2 is inapproximable even in quasipolynomial time, in the sense that for large l there is no quasipolynomial algorithm that can distinguish between the two
mutually exclusive cases 1) and 2). To see that these cases are
indeed mutually exclusive for large l, observe that q1 (l) > 1
1−δ
when l is large, because q1 (l) = 2Ω(log l).
C. Sketch of Proof of Theorem 1
We begin by sketching the intuition behind the proof of
Theorem 1. Our general approach is to find instances of
Problem 1 that are as hard as inapproximable instances of
the variable selection Problem 2. We begin by discussing a
construction that does not work, and then explain how to fix it.
Given the matrix U coming from a variable selection
Problem 2, we first attempt to construct an instance of the
minimal reachability Problem 1 where:
• the system’s initial condition is x(t0 ) = 0;
⊤
• the destination state x1 at time t1 is of the form [1, 0]
(the exact dimensions of 1 and 0 are to be determined);
• the input matrix is B = I;
• the system matrix A is


0 U
A=
,
(3)
0 0
where the number of zeros is large so that A2 = 0.
Whereas the variable selection problem involves finding the
smallest set of columns of U so that a certain vector is in
their span, for the minimum reachability problem, every time
we add the k-th state to the set of actuated variables S, the
2 In this context, a function with a fractional exponent is considered to be
a polynomial, e.g., l1/5 is considered to be a polynomial in l.

5

reachability span expands by adding the span of the set of
columns of the controllability matrix that correspond to the
vector ek being added in I(S). In particular, for the above
construction, because A2 = 0, when the k-th state is added to
the set of actuated variables, the span of the two columns ek
and U ek is added to the reachability space.
In other words, with the above construction we are basically
constrained to make “moves” which add columns in pairs,
and we are looking for the smallest number of such “moves”
making a certain vector lie in the span of the columns.
It should be clear that there is a strong parallel between this
and variable selection (where the columns are added one at a
time). However, because the columns are being added in pairs,
this attempt to connect minimum reachability with variable
selection does not quite work. To fix this idea, we want only
the columns of U to contribute meaningfully to the addition
of the span, with any vectors ek we add along the way being
redundant; this would reduce minimal reachability to exactly
variable selection. We accomplish this by further defining:


U
 U 


U′ =  .  ,
 .. 
U

where we stack U some large
termined in the main proof of
We then set:

0
A=
0

number of times (to be deTheorem 1 at Section V-D).

U′
.
(4)
0

The idea is because U is stacked many times, adding a column
of U to a set of vectors expands the span much more than
adding any vector ek , so there is never an incentive to consider
the contributions of any ek to the reachability space.
We make the aforementioned construction of the system matrix A precise: given a matrix M ∈ Rm×l, for n ≥ max{m, l}d
we define φn,d (M ) to be the n × n matrix which stacksM in
the top-right hand corner d times. For example,


0 0 0 1 2
 0 0 0 3 4 




1 2

M=
, φ5,2 (M ) = 
 0 0 0 1 2 ,
3 4
 0 0 0 3 4 
0 0 0 0 0
i.e., φ5,2 (M ) stacks M twice, and then pads it with enough
zeros to make the resulting matrix 5 × 5. Observe that
φn,d (M )2 = 0 for n ≥ max{m, l}(d + 1). Overall, in the
next section, we set A = φn,d (U ) for large enough d, and
n = max{m, l}(d + 1), and we prove Theorem 1.
D. Proof of Theorem 1
Adopting the notation in Theorem 2, we focus on problem
instances where for large enough l it is q1 (l) > 1, per the
proof of Theorem 2, i.e., of [29, Theorem 2]. In addition, we
let d = ⌈p1 (l)q1 (l)⌉, and n = max{m(l), l}(d+1). Moreover,
for simplicity, we use henceforth m and m(l) interchangeably.
Finally, we consider the instances of Problem 1 where:
• the initial condition is x(t0 ) = 0n ;

⊤
⊤
the destination state x1 at time t1 is [1⊤
md , 0n−md ] ;
• the input matrix is B = I, where I is the identity matrix;
• the system matrix is A = φn,d (U ).
Given the above, to prove Theorem 1 we first define the
following four statements:
S1) There exists a vector y ∈ Rl such that U y = 1m and
||y||0 ≤ p1 (l).
S2) For any vector y ∈ Rl such that ||U y − 1m ||22 ≤ ∆(l),
we have ||y||0 ≥ p1 (l)q1 (l).
′
S1 ) There exists a set S ⊆ {1, 2, . . . , n} with |S| ≤ p1 (l)
⊤
⊤
such that the state x1 = [1⊤
md , 0n−md ] is reachable.
′
S2 ) There is no set S ⊆ {1, 2, . . . , n} with cardinality strictly
less than p1 (l)q1 (l) that makes reachable some x
b1 with
⊤
⊤ 2
||b
x1 − [1⊤
md , 0n−md ] ||2 ≤ ∆(l).
Recall that in Section V-B we stated that the statements S1S2 are mutually exclusive for q1 (l) > 1 (which is the case for
the instances we consider in this proof), and that Theorem 2
implies there is no quasi-polynomial algorithm (unless NP∈
BPTIME(npoly log n )) that can distinguish between S1 and S2.
Given the above, we next proceed with the proof of Theorem 1 by proving first that statement S1 implies statement S1′ ,
and then that also statement S2 implies statement S2′.
Proof that statement S1 implies statement S1′ : We prove
that if statement S1 is true, then statement S1′ also is. In
particular, suppose there exists a vector y ∈ Rl with U y =
1m and ||y||0 ≤ p1 (l) (statement S1). In this case, we claim
there exists a set S ⊆ {1, 2, . . . , n} with |S| ≤ p1 (l) such that
⊤
⊤
′
x1 =[1⊤
md , 0n−md ] is reachable (statement S1 ). Indeed, let
S be a set of columns of U that have 1m in their span, and
set S = {k + n − l | k ∈ S}. Then |S| ≤ p1 (l), and
X
1m =
yk Uk ,
(5)
•

k∈S

where yk denotes the k-th element of the vector y, and Uk
denotes the k-th column of the matrix U . Due to eq. (5), we
⊤
⊤
can rewrite the vector x1 =[1⊤
md , 0n−md ] as follows:




yk Uk
1m



 

 1m  X  yk U k 
1md




.
.
..
..
=

=

0n−md




 1m  k∈S  yk Uk 
0n−md
0n−md
X
=
yk Ak+n−l ,
(6)
k∈S

where the vector 1m in the second term from the left is
repeated ⌈p1 (l)q1 (l)⌉ times, since d = ⌈p1 (l)q1 (l)⌉, and
where the final step (eq. (6)) follows by definitions of A as
A = φn,d (U ), and where Ak+n−l denotes the (k + n − l)-th
column of A. Now, each of the vectors Ak+n−l in the last
⊤
⊤
term is a column of AI(S), so [1⊤
md , 0n−md ] indeed lies in
the range of the controllability matrix and, as a result, the state
⊤
⊤
x1 = [1⊤
md , 0n−md ] is reachable by actuating S.
Proof that statement S2 implies statement S2′ : We prove
that if the statement S2 is true, then the statement S2′ also is.
In particular, per statement S2 suppose that any vector y with
||U y − 1m ||22 ≤ ∆(l) has the property that ||y||0 ≥ p1 (l)q1 (l).

6

We claim that in this case there is no set S ⊆ {1, 2, . . . , n}
with cardinality strictly less than p1 (l)q1 (l) that makes reach⊤
⊤ 2
able some x
b1 with ||b
x1 −[1⊤
md , 0n−md ] ||2 ≤ ∆(l) (statement
′
S2 ). To prove this, assume the contrary, i.e., assume there
exists S with cardinality strictly less than p1 (l)q1 (l) that makes
⊤
⊤ 2
reachable some x
b1 with ||b
x1 −[1⊤
md , 0n−md ] ||2 ≤ ∆(l) —we
call this assumption A1. We obtain a contradiction as follows:
the pigeonhole principle implies that in the set {1, 2, . . . , md}
there is some interval E = {κm + 1, κm + 2, . . . , κm + m},
where κ is a non-negative integer, such that S∩E = ∅, because
|S| < p1 (l)q1 (l) and md ≥ m⌈p1 (l)q1 (l)⌉. Define the vector
x
bE ∈ Rm by taking the rows of x
b1 corresponding to indexes
in E. Then,
||[b
xE − 1m ||22 ≤ ∆(l),

⊤
⊤ 2
since x
b1 with ||b
x1 − [1⊤
md , 0n−md ] ||2 ≤ ∆(l). Moreover,
we next prove that x
bE is in the span of |S| columns of U .
To this end, we make the following observations: since x
b1 is
reachable, it is:

x
b1 ∈ Range[I(S), AI(S), A2 I(S), . . . , An−1 I(S)] =
Range[I(S), AI(S)],

(7)

2

where the equality in eq, (7) holds since A = 0. Now, eq. (7)
implies there exists a vector z such that:
[I(S), AI(S)]z = x
b1 .

(8)

If we break up the set S into two sets, (i) the set of indexes
corresponding to A’s first n − l columns, which we denote
henceforth by S1:n−l , and (ii) the set of indexes corresponding to A’s last l columns, which we denote henceforth by
Sn−l+1:n , such that S = S1:n−l ∪ Sn−l+1:n , and recall A’s
definition, we can write the term AI(S) in eq. (8) as follows:



0 U′
I(S1:n−l )
0
AI(S) =
0 0
0
I(Sn−l+1:n )


′
0 U I(Sn−l+1:n )
=
,
(9)
0
0
where U ′ is, per the definition of A, the matrix that is created
by stacking d copies of U the one on top of the other.
Therefore, using this definition of U ′, the term U ′ I(Sn−l+1:n )
in eq. (9) is re-written as follows:


U I(Sn−l+1:n )
 U I(Sn−l+1:n ) 


U ′ I(Sn−l+1:n ) = 
(10)
,
..


.
U I(Sn−l+1:n )

where the term U I(Sn−l+1:n ) is repeated d times. Let now z1
be the vector that is constructed by z by keeping all the
elements of z that in eq. (8) multiply the matrix I(S), and
let z2 be the vector that is constructed by z by keeping all the
elements of z that in eq. (8) multiply the non-zero part of the
matrix AI(S), which is stated in eq. (10). Then, due to eq. (9)
and eq. (10), the eq. (8) gives:


U I(Sn−l+1:n )z2
 U I(Sn−l+1:n )z2 




..
b1 ,
(11)
I(S)z1 + 
=x
.


 U I(Sn−l+1:n )z2 
0

Moreover, x
bE , due to its definition, is in the span of the vectors
obtained by taking the rows κm + 1, . . . , κm + m of the
columns of the reachability matrix [I(S), AI(S)]; in particular,
since it is S ∩ E = ∅, from eq. (11) we get:
U I(Sn−l+1:n )z2 = x
bE ,

(12)

and indeed we have shown that the vector x
bE is in the span of
at most |S| columns of U (eq. (12)). The contradiction is now
obtained because assumption A1 tells us that |S| < p1 (l)q1 (l)
while the statement S2 (which we have assumed initially to
hold) tells us the opposite. As a result, the truth of statement
S2 implies the truth of statement S2′.
In sum, we proved that the statement S1 implies the
statement S1′ , as well as, that the statement S2 implies the
statement S2′ and, as a result, we showed how Problem 1 can
be reduced to the (inapproximable in quasi-polynomial time)
Problem 2. Moreover, the reduction is made in polynomial
time, since all involved matrices are of polynomial size in l.
We complete Theorem 1’s proof with the steps below:
• Recall
that Theorem 2 shows that, unless
NP∈BPTIME(npoly log n ), no quasi-polynomial time
algorithm can distinguish between the statements S1 and
S2; this implies that, under the same assumption, no
quasi-polynomial time algorithm can distinguish between
the statement S1′ and the statement S2′.
Ω(log1−δ l)
• Since for any δ ∈ (0, 1) we can take q1 (l) = 2
in Theorem 2, this implies that the smallest number
⊤
of inputs rendering [1⊤
md , 0n−dm ] reachable cannot be
approximated within a multiplicative factor of q1 (l).
Indeed, any algorithm which gives an approximation of
the smallest number of inputs with a multiplicative factor
smaller than q1 (l) would make it possible to distinguish
between case S1′ and case S2′. By Theorem 2, the
1−δ
inapproximability factor q1 (l) grows as 2Ω(log l), and
since l can be upper and lower bounded by a polynomial
in n (since n ≥ l, and n is at most polynomial in l), we
1−δ
set ∆2 (n) = 2Ω(log n) in the statement of Theorem 1.
• Since ∆(l) is a polynomial in l, as well as, l ≤ n, we
may replace ∆(l) by some polynomial ∆1 (n), as in the
statement of Theorem 1.
VI. C ONCLUDING R EMARKS
We focused on the minimal reachability Problem 1, which
is a fundamental question in optimization and control with
applications such as power systems and neural circuits. By exploiting the connection to the variable selection Problem 2,
we proved that Problem 1 is hard to approximate. Future
work will focus on properties for the system matrix A so that
Problem 1 is approximable in polynomial time.
We conclude with an open problem. As we have discussed, the minimum reachability problem is (0, 2log n )approximable by the algorithm which actuates every variable;
1−δ
but (0, 2O(log n) ) is impossible for any positive δ. We
wonder, therefore, whether the minimum number of actuators
can
of say,
√ be approximated to within a multiplicative factor
c
n in polynomial time, or, more generally,
n
for
some
√
c ∈ (0, 1). Indeed, observe that since n = 2(1/2) log n, the

7

√
1−δ
function n does not belong to 2O(log n) for any δ > 0.
Thus, the present paper does not rule out the possibility of
approximating
the minimum reachability problem up to a
√
factor of n, or more broadly, nc for c ∈ (0, 1). We remark
that such an approximation guarantee would have considerable
repercussions in the context of effective control, as at the
moment the best polynomial-time protocol for actuation to
meet a reachability goal (in terms of worst-case approximation
guarantee) is to actuate every variable.
R EFERENCES
[1] Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási, “Controllability of complex
networks,” Nature, vol. 473, no. 7346, p. 167, 2011.
[2] F. Muller and A. Schuppert, “Few inputs can reprogram biological
networks,” Nature, vol. 478, no. 7369, pp. E4–E4, 2011.
[3] T. Zhou, “Minimal inputs/outputs for a networked system,” IEEE
Control Systems Letters, vol. 1, no. 2, pp. 298–303, 2017.
[4] A. Clark, B. Alomair, L. Bushnell, and R. Poovendran, “Minimizing
convergence error in multi-agent systems via leader selection: A supermodular optimization approach,” IEEE Transactions on Automatic
Control, vol. 59, no. 6, pp. 1480–1494, 2014.
[5] A. Clark, L. Bushnell, and R. Poovendran, “A supermodular optimization
framework for leader selection under link noise in multi-agent systems,”
IEEE Trans. on Automatic Control, vol. 59, no. 2, pp. 283–296, 2014.
[6] A. Olshevsky, “Minimal controllability problems,” IEEE Transactions
on Control of Network Systems, vol. 1, no. 3, pp. 249–258, 2014.
[7] S. Pequito, S. Kar, and A. P. Aguiar, “A framework for structural
input/output and control configuration selection in large-scale systems,”
IEEE Trans. on Automatic Control, vol. 61, no. 2, pp. 303–318, 2016.
[8] F. Pasqualetti, S. Zampieri, and F. Bullo, “Controllability metrics,
limitations and algorithms for complex networks,” IEEE Transactions
on Control of Network Systems, vol. 1, no. 1, pp. 40–52, 2014.
[9] T. H. Summers, F. L. Cortesi, and J. Lygeros, “On submodularity and
controllability in complex dynamical networks,” IEEE Transactions on
Control of Network Systems, vol. 3, no. 1, pp. 91–101, 2016.
[10] V. Tzoumas, M. A. Rahimian, G. J. Pappas, and A. Jadbabaie, “Minimal
actuator placement with bounds on control effort,” IEEE Transactions
on Control of Network Systems, vol. 3, no. 1, pp. 67–78, 2016.
[11] Y. Zhao, F. Pasqualetti, and J. Cortés, “Scheduling of control nodes
for improved network controllability,” in Proceedings of the IEEE 55th
Conference on Decision and Control, 2016, pp. 1859–1864.
[12] S. Pequito, G. Ramos, S. Kar, A. Aguiar, and J. Ramos, “Robust minimal
controllability problem,” Automatica, vol. 82, pp. 261–268, 2017.
[13] V. Tzoumas, K. Gatsis, A. Jadbabaie, and G. J. Pappas, “Resilient
monotone submodular function maximization,” in Proceedings of the
IEEE 56th Annual Conference on Decision and Control, 2017, to appear.
[14] V. Tzoumas, A. Jadbabaie, and G. J. Pappas, “Sensor placement for
optimal kalman filtering,” in Proceedings of the American Control
Conference, 2016, pp. 191–196.
[15] ——, “Near-optimal sensor scheduling for batch state estimation,” in
Proceedings of the IEEE 55th Conference on Decision and Control,
2016, pp. 2695–2702.
[16] H. Zhang, R. Ayoub, and S. Sundaram, “Sensor selection for kalman
filtering of linear dynamical systems: Complexity, limitations and greedy
algorithms,” Automatica, vol. 78, pp. 202–210, 2017.
[17] L. Carlone and S. Karaman, “Attention and anticipation in fast visualinertial navigation,” in Proceedings of the IEEE International Conference on Robotics and Automation, 2017, pp. 3886–3893.
[18] M. Amin and J. Stringer, “The electric power grid: Today and tomorrow,”
MRS bulletin, vol. 33, no. 04, pp. 399–407, 2008.
[19] Z. Liu, A. Clark, P. Lee, L. Bushnell, D. Kirschen, and R. Poovendran,
“MinGen: Minimal generator set selection for small signal stability in
power systems: A submodular framework,” in Proceedings of the IEEE
55th Conference on Decision and Control, 2016, pp. 4122–4129.
[20] California Partners for Advanced Transit and Highways, 2006. [Online].
Available: http://www.path.berkeley.edu/
[21] S. Gu et al., “Controllability of structural brain networks,” Nature
communications, vol. 6, p. 8414, 2015.
[22] C. Tu, R. P. Rocha, M. Corbetta, S. Zampieri, M. Zorzi, and S. Suweis,
“Warnings and Caveats in Brain Controllability,” ArXiv e-prints, 2017.
[23] V. Tzoumas, A. Jadbabaie, and G. J. Pappas, “Minimal reachability
problems,” in Proceedings of the IEEE 54th Annual Conference on
Decision and Control, 2015, pp. 4220–4225.

[24] Z. Liu, A. Clark, P. Lee, L. Bushnell, D. Kirschen, and R. Poovendran,
“Towards scalable voltage control in smart grid: A submodular optimization approach,” in Proceedings of the 7th International Conference
on Cyber-Physical Systems, 2016, p. 20.
[25] M. Sviridenko, J. Vondrák, and J. Ward, “Optimal approximation for
submodular and supermodular optimization with bounded curvature,”
in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on
Discrete Algorithms. SIAM, 2014, pp. 1134–1148.
[26] S. Arora and B. Barak, Computational complexity: a modern approach.
Cambridge University Press, 2009.
[27] G. Nemhauser, L. Wolsey, and M. Fisher, “An analysis of approximations
for maximizing submodular set functions – I,” Mathematical Programming, vol. 14, no. 1, pp. 265–294, 1978.
[28] C.-T. Chen, Linear System Theory and Design, 3rd ed. New York, NY,
USA: Oxford University Press, Inc., 1998.
[29] D. Foster, H. Karloff, and J. Thaler, “Variable selection is hard,” in
Proceedings of the Conference on Learning Theory, 2015, pp. 696–709.

