Showing a problem on a specific graph is NP-hard

Maybe there is a trivial answer to my question or maybe there is not any. But I ask it here and appreciate if anyone can give me a clear answer.

We know that a set of problems like minimum clique cover problem, coloring problem, vertex cover, ... are NP-hard for general graphs, but maybe polynomial-time solvable for specific graphs.

My question is that, if we are given a graph $G=(V,E)$ (I am asking this generally but you can specifically assume the graph described here), and want to find for example minimum clique cover for this graph, how can we show that it is NP-hard (if it is)? Is there any method for that?

There's no such thing as a hard instance. You can always figure out the answer to that one instance and then hard-code that into an algorithm. For example, you can always have an algorithm for SAT that says

if input="(XvY)^(!Xv!YvZ)"
    return SATISFIABLE
else
    [loop through all possible variable assignments]

Incidentally, this is why nobody looks at "best-case complexity", since any algorithm can be adapted to run in best-case constant time in this way. (Constant because you only have to read a fixed amount of the input to see if it's one of the ones that you have a hard-coded answer for.)

There's a category error in asking if an instance can be NP-complete. Recall the definition of what NP-completeness is:


A language $L$ is NP-complete if is in NP and every other language in NP is polynomial-time many–one reducible to $L$.

First, that statement doesn't "type-check" if you try to make $L$ be a string rather than a language. Second, the definition of many–one reductions requires that you have at least one "yes" instance and at least one "no" instance to use as targets for the reduction. One instance isn't enough to make these definitions work.

StackExchange Computer Science Q#69092, answer score: 7