I'm interested in whether it's possible to express the hardness of a result in the following form.
1.For example: Suppose $A(n)$ is the class of graphs for which the minimum degree $\delta(G)\geq n/2$ where $n$ is the number of vertices. Then does it make sense to say e.g the maximum clique problem is NP-hard for the class $A(n)$?
Note, i'm not really interesting in whether the max clique problem is actually hard, just whether it makes sense formally to express a result in this way. The main reason i'm interested in this is because i'm expressing hardness for a class of graphs where the input of a graph is a parameter which defines the class.
- Supposing the answer to question 1 is yes and it does make sense to express hardness in this form, is all that is required to prove hardness just a reduction (in the usual sense) which constructs a graph in which the degree of each vertex is larger than $n/2$?
I apologise if the question is poorly written, and i really appreciate any clarification on the issues!
1) Yes- your formalization makes sense. Is $A(n)$ NP-Hard for an arbitrary fixed $n \in \mathbb{N}$? I don't know.
2) A reduction from an existing NP-Hard problem $L$ to $A(n)$ would suffice. Note that for each instance $\omega \in L$, you must transform $\omega$ to a graph in $A(n)$. Furthermore, your transformation cannot take any string not in $L$ to a graph in $A(n)$.
One formalization of the CLIQUE problem is as follows:
INSTANCE: Let $G$ be a graph and let $k \in \mathbb{N}$.
DECISION: Does $G$ contain a clique of order $k$?
In this manner, the CLIQUE problem is not restricted to a fixed clique-size. It can be easier to show NP-Hardness of a larger class of problem, which makes this formalization appealing (such as when reducing from CNF-SAT).
You may find a similar formalization helpful in your own work.