I'm considering a very interesting problem. For a graph $G=(V,E)$, either directed or undirected, if we define \begin{equation} \rho(G)=\max\{|\lambda|\;|\;\lambda\text{ eigenvalue of $G$'s adjacency matrix} \} \end{equation} then we could define a set function $F$, which maps every subgraph $\tilde{G}$ of $G$ to $\rho(\tilde{G})$.
Given a $k$ ($0<k<|V|$), what I am primarily considering is the following: can we find a the subgraph of $G$ with smallest $F$ value in the set of all subgraphs in $G$ with $|V|-k$ nodes? If not, can we find one with certain approximation factor?
My Thinking
A very natural way is a greedy method, i.e., iteratively delete one node that decreases the set function value the most, remove the node and renew the graph, stop when I have deleted $k$ nodes. However, this set function seems not neither be submodular nor supermodular. So my question is, could this greedy method have some approximation rate close to optimal?
I will appreciate it so much if someone can give me some enlightenment!