Hendrych's NP-hardness conjecture for Bayesian A-optimal design

Proof with an encoding-explicit binary reduction

The conjecture is proved as Theorem 1 of Yongchun Li's Strong Formulations and Algorithms for Regularized A-optimal Design. Since regularized A-optimal design (RAOD) is the isotropic-prior special case of Bayesian AOD, its NP-hardness implies the conjecture.

Here is a reduction using only a square binary design matrix and the fixed regularization parameter $\lambda=1$.

Let $G$ be a simple graph on $V=\{1,\ldots,n\}$, with $n\geq2$, and set

$$D=n^2.$$

Construct a matrix $B\in\{0,1\}^{D\times D}$. Its rows are indexed by ordered pairs $(u,v)\in V^2$. Its first $n$ columns correspond to the vertices; its remaining $D-n$ columns are zero.

For every unordered pair $u<v$:

• if $\{u,v\}\in E(G)$, row $(u,v)$ has ones in columns $u$ and $v$, while row $(v,u)$ is zero;
• if $\{u,v\}\notin E(G)$, row $(u,v)$ has a single one in column $u$, while row $(v,u)$ has a single one in column $v$.

Every row $(u,u)$ is zero. It follows directly that

$$B^{\mathsf T}B = \bigl((n-1)I_n+\operatorname{Adj}(G)\bigr)\oplus 0_{D-n}.$$

Regard the columns of $B$ as the design vectors and set $\lambda=1$. Choose $k\leq n$ experiments. For a set $S$ of $k$ columns, let

$$T=S\cap V,\qquad r=|T|,\qquad t=k-r.$$

After simultaneously permuting rows and columns,

$$B_S^{\mathsf T}B_S+I_k \cong \bigl(nI_r+\operatorname{Adj}(G[T])\bigr)\oplus I_t.$$

Let $\sigma_1,\ldots,\sigma_r$ be the positive eigenvalues of the first block. Their sum is $rn$, so the arithmetic-harmonic mean inequality gives

$$\sum_{i=1}^r\frac1{\sigma_i}\geq\frac rn.$$

Equality holds exactly when every $\sigma_i=n$, equivalently when

$$\operatorname{Adj}(G[T])=0,$$

so exactly when $T$ is independent.

Consequently,

$$\operatorname{tr}\!\left((B_S^{\mathsf T}B_S+I_k)^{-1}\right) \geq \frac rn+t.$$

If $t>0$, then

$$\frac rn+t-\frac kn=t\left(1-\frac1n\right)>0.$$

Therefore

$$\operatorname{tr}\!\left((B_S^{\mathsf T}B_S+I_k)^{-1}\right)\geq\frac kn,$$

with equality exactly when $S$ consists of $k$ original vertex columns forming an independent set.

Finally, $B_SB_S^{\mathsf T}$ and $B_S^{\mathsf T}B_S$ have the same nonzero eigenvalues, giving

$$\operatorname{tr}\!\left((B_SB_S^{\mathsf T}+I_D)^{-1}\right) = D-k+ \operatorname{tr}\!\left((B_S^{\mathsf T}B_S+I_k)^{-1}\right).$$

Thus, with the rational threshold

$$\tau=D-k+\frac kn,$$

there exists a size-$k$ selection with objective at most $\tau$ if and only if $G$ has an independent set of size $k$.

The construction has polynomial size, all design entries lie in $\{0,1\}$, and $\lambda=1$. This is a polynomial-time reduction from Independent Set, proving RAOD NP- hard. Since RAOD is a special case of Bayesian AOD, Hendrych's conjecture follows.

Source, especially Theorem 1 and Appendix A.2: https://arxiv.org/abs/2505.14957