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?
Showing a problem on a specific graph is NP-hard
complexity theory;graphs;np complete;np hard
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 saysif input=(XvY)^(!Xv!YvZ)    return SATISFIABLEelse    [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.