We know that a submodular maximization problem of the form $$ \mathcal{P}: \,\, \mathop {\max }\limits_S f\left( S \right) $$ where $f(S)$ is a submodular set function, is NP-hard (Claim 1).
This claim can be proven by reduction from a well-known NP-hard problem such as Minimum Vertex Cover (MVC) [1], i.e., showing that the objective function in MVC problem is submodular.
Can you please help me with the two questions below:
Does Claim 1 means that "every instance" of a submodular maximization problem is NP-hard? Or does it simply imply that the general class of submodular maximization is NP-hard?
Now that I have a specific instance of a submodular maximization problem $$ \mathcal{P1}: \,\, \mathop {\max }\limits_S f_1\left( S \right) $$ Can we (and how to) prove that $\mathcal{P1}$ is NP-hard?
[1] Rolnick, David, and Jonathan Weed. "Greedy Maximization of Submodular Functions." (2014).