# How to minimize this set function?

I'm considering a very interesting problem. For a graph $$G=(V,E)$$, either directed or undirected, if we define $$$$\rho(G)=\max\{|\lambda|\;|\;\lambda\text{ eigenvalue of G's adjacency matrix} \}$$$$ then we could define a set function $$F$$, which maps every subgraph $$\tilde{G}$$ of $$G$$ to $$\rho(\tilde{G})$$.

Given a $$k$$ ($$0), 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!

• What is meant by "[...] which function every subgraph $\tilde G$ of $G$ to $ρ(\tilde G)$"? Is a verb missing? Commented Apr 16, 2023 at 17:06
• Thank you @pluton, this "function" is a verb, means "maps", i.e., $F:\tilde{G}\rightarrow \rho(\tilde{G})$, sorry for not clearly writen Commented Apr 16, 2023 at 17:17
• Still welcome some valuable comments! Commented Apr 19, 2023 at 19:09