The only graph problem that I worked with is TSP. It is exponentially hard, but there are tons of heuristics which allows to find near to optimum solution.
So I was wondering, is there any graph problems (or optimization problems which could be mapped onto graph) that are exponentially hard and can not be solved (even approximatly) efficiently for small and mid-sized systems? (let's say 10-20 verticies)
I recommend you look at a list of NP-complete problems on graphs. For each one, research whether there exists a known approximation algorithm. For some problems we have hardness of approximation results (which say that there is no polynomial-time algorithm that achieves approximation factor $\alpha$, unless $P=NP$). Those are potential candidates that might be of interest. In particular, I'd recommend you study the standard methods for dealing with intractability, then look for a candidate problem where none of those seem to work. You might also look at graph problems that are APX-complete as candidates worthy of further exploration.
For instance, graph coloring might be a possible candidate to look at. I haven't studied that problems so I don't know whether good heuristics exist. I doubt it will be hard on graphs with only 10-20 vertices, but it might be hard with somewhat larger graphs.
